چیزی که تو کتاب طراحی الگوریتم پارسه به عنوان راه حلش توضیح داده اینجوریه که:

ما ابتدا تمام داده‌ها بر حسب صعودی مرتب می کنیم یعنی تو یک مجموعه هم زمان شروع و هم زمان پایان رو داریم که به ترتیب صعودی هستن

دو پشته در نظر میگیریم‌: یکی برای کلاس های پر و دیگری برای کلاس های خالی

مجموعه را پیمایش میکنیم اگر به یک زمان شروع رسیدیم‌، یک کلاس از پشته‌ی کلاس های خالی pop کرده و در پشته‌ی کلاس های خالی push میکنیم
و اگر به زمان پایان رسیدیم، بر عکس عمل میکینم و یک کلاس از پشته‌ی پر بر میداریم و در پشته‌ی خالی میگذاریم
تعداد کلاس هایی که در پشته‌ی کلاس های پر قرار میدهیم برابر کمترین تعداد کلاس هاست

و چون زمان push و pop حداکثر میشه [tex]O(n)[/tex] پس زمان کل برابر با همون زمان مرتب سازی میشه یعنی:
[tex]O(nlogn)[/tex]

خوب دوست من مثل انتخاب فعالیت‌ها یا همون سخران‌ها قبلا کس دیگه ای پرسیده بود نمیدانم کجا ولی لینکش بود
به هر حال
شما فعالیت هارا با یه جستجوی مقایسه ای بر حسب زمان پایان مرتب میکنید که میشه nlogn
بعد توی حلقه یه دستور ایف میزاری و چک میکنی ایا زمان شروع کلاس یعدی از زمان پایان کلاس قبلی بیشتر هست ایا؟
اگر بیشتر بود اون زمان به کلاس اختصاص داده میشود
nlogn+n
=
nlogn

ممنون از جوابتان ولی دارید اشتباه می کنید انتخاب فعالیت هایی که در کتاب گفته شده با این یک فرق کوجکی دارد
مثلا اگر همان سخنرانها را در نظر ب*****ید صورت سوال جنین است
یک سالن سخنرانی داریم و تعدادی سحنران می خواهیم حداکتر سخنرانی های بدون تداخل را در این سالن برگزار کنیم
ولی سوال پرسیده شده با تبذیل به مضمون متال بالا به این صورت است
تعدادی سخنران داریم می خواهیم حتما همه سخنرانها سخنرانی کنند حداقل تعداد سالتهایی که می شود تخصیص داد تا این امر محقق شود
شما را به خدا اگر کسی جواب این سوال را می داند بگوید

توی تقسیم و غلبه هم این مسئله رو داشتیم که ممکنه همیشه یک آرایه به ۲ نیم تقسیم نشه و میتونه به چند بخش تقسیم بشه و هر بخش هم به طور بازگشتی به بخشهای دیگه تقسیم بشه.که این روش هم از مرتبه nlogn هست

اون چیزی که من به ذهنم میرسه اینه که ما میتونیم از روش مسئله‌ی سخنرانی‌ها استفاده کنیم.

اونجا ما حداکثر مجموعه‌ی غیر هم پوشان برای سخنرانی‌ها رو انتخاب میکنیم اینجا هم همین کار رو میکنیم زیرا اعضای این مجموعه میتونن تو یک کلاس بر گزار بشن حالا اینا رو از مجموعه اصلی حذف میکنیم و دوباره بین باقی مونده‌ها باز حداکثر رو پیدا میکنیم به همین ترتیب تا مجموعه خالی بشه.

نظرتون چیه؟؟؟؟

(۰۶ بهمن ۱۳۹۰ ۱۲:۱۴ ق.ظ)homa نوشته شده توسط:  اون چیزی که من به ذهنم میرسه اینه که ما میتونیم از روش مسئله‌ی سخنرانی‌ها استفاده کنیم.

اونجا ما حداکثر مجموعه‌ی غیر هم پوشان برای سخنرانی‌ها رو انتخاب میکنیم اینجا هم همین کار رو میکنیم زیرا اعضای این مجموعه میتونن تو یک کلاس بر گزار بشن حالا اینا رو از مجموعه اصلی حذف میکنیم و دوباره بین باقی مونده‌ها باز حداکثر رو پیدا میکنیم به همین ترتیب تا مجموعه خالی بشه.

نظرتون چیه؟؟؟؟

با تشکر از جوابتان
هر بار اجرای الگوریتم برای یافتن حداکثر مجموعه‌ی غیر هم پوشان O(N) اگر فرض کنیم همه N محموعه همپوشانی داشته باشند مجبوربم N بار الگوریتم را تا رسیدن به محموعه خالی تکرار کنیم که میشه N^2
کسی راه حل دیگری ندارد لطفا جواب بدید

ممنون از جوابتان
ییخشید که گیجم ممکن این سوال را با این متال حل کنید
(۱و۳)
(۲و۴)
(۵و۶)
(۷و۱۰)
(۸و۹)
اینکه کفتید داده‌ها را مرتب کردید منظورتان این هست اول بر اساس زمان شروع بعد بر اساس زمان پایان مرتب می کنید؟

(۰۶ بهمن ۱۳۹۰ ۰۷:۴۲ ب.ظ)rad.bahar نوشته شده توسط:  ممنون از جوابتان
ییخشید که گیجم ممکن این سوال را با این متال حل کنید
(۱و۳)
(۲و۴)
(۵و۶)
(۷و۱۰)
(۸و۹)
اینکه کفتید داده‌ها را مرتب کردید منظورتان این هست اول بر اساس زمان شروع بعد بر اساس زمان پایان مرتب می کنید؟

همه داده‌ها رو در نظر میگیری چه زمان شروع و چه زمان پایان ولی میفهمی کدومش شروع هست و کدوم پایان.
اینجا به طور کلی ۱۰ تا عدد داری با [tex]O(nlogn)[/tex] مرتب میکنی ارایه میشه:
[tex]\left \{1_{s},2_{s},3_{f},4_{f},5_{s},6_{f},7_{s},8_{s},9_{f},10_{f} \right.\left. \right \}[/tex]

حالا ارایه رو از اول پیمایش میکنی و هر وقت به داده ایی مربوط به زمان شروع رسیدی یک کلا س میذاری داخل پشته و هر وقت هم یک داده مربوط به زمان پایان دیدی یک کلاس از داخل پشته‌ی کلاس‌ها pop میکنی .
حداکثر کلاس هایی که داخل پشته گذاشتی میشه حداقل کلاس ها
تو این مثال پشته حدا کثر به اندازه ۲ پر میشه.
حالا ممکنه بعضی وقتها خالی بشه یا اینکه فقط یکی تو پشته باشه اما مهم اینه که یک بار ما ۲ تا کلاس تو پشته داشتیم.