n بازه i =[xi,yi که ۱<i و i<n داده شده اند هر بازه نشاندهنده زمان یک کلاس ذرس است کمترین تعداد اتاق لارم که بدون تداخل به همه کلاس‌ها اتاق داده شود
چواب n*logn
خوب دوست من مثل انتخاب فعالیت‌ها یا همون سخران‌ها قبلا کس دیگه ای پرسیده بود نمیدانم کجا ولی لینکش بود
به هر حال
شما فعالیت هارا با یه جستجوی مقایسه ای بر حسب زمان پایان مرتب میکنید که میشه nlogn
بعد توی حلقه یه دستور ایف میزاری و چک میکنی ایا زمان شروع کلاس یعدی از زمان پایان کلاس قبلی بیشتر هست ایا؟
اگر بیشتر بود اون زمان به کلاس اختصاص داده میشود
nlogn+n
=
nlogn
ممنون از جوابتان ولی دارید اشتباه می کنید انتخاب فعالیت هایی که در کتاب گفته شده با این یک فرق کوجکی دارد
مثلا اگر همان سخنرانها را در نظر ب*****ید صورت سوال جنین است
یک سالن سخنرانی داریم و تعدادی سحنران می خواهیم حداکتر سخنرانی های بدون تداخل را در این سالن برگزار کنیم
ولی سوال پرسیده شده با تبذیل به مضمون متال بالا به این صورت است
تعدادی سخنران داریم می خواهیم حتما همه سخنرانها سخنرانی کنند حداقل تعداد سالتهایی که می شود تخصیص داد تا این امر محقق شود
شما را به خدا اگر کسی جواب این سوال را می داند بگوید
توی تقسیم و غلبه هم این مسئله رو داشتیم که ممکنه همیشه یک آرایه به ۲ نیم تقسیم نشه و میتونه به چند بخش تقسیم بشه و هر بخش هم به طور بازگشتی به بخشهای دیگه تقسیم بشه.که این روش هم از مرتبه nlogn هست
اون چیزی که من به ذهنم میرسه اینه که ما میتونیم از روش مسئله‌ی سخنرانی‌ها استفاده کنیم.
اونجا ما حداکثر مجموعه‌ی غیر هم پوشان برای سخنرانی‌ها رو انتخاب میکنیم اینجا هم همین کار رو میکنیم زیرا اعضای این مجموعه میتونن تو یک کلاس بر گزار بشن حالا اینا رو از مجموعه اصلی حذف میکنیم و دوباره بین باقی مونده‌ها باز حداکثر رو پیدا میکنیم به همین ترتیب تا مجموعه خالی بشه.
نظرتون چیه؟؟؟؟
(۰۶ بهمن ۱۳۹۰ ۱۲:۱۴ ق.ظ)homa نوشته شده توسط: اون چیزی که من به ذهنم میرسه اینه که ما میتونیم از روش مسئله‌ی سخنرانی‌ها استفاده کنیم.با تشکر از جوابتان
اونجا ما حداکثر مجموعه‌ی غیر هم پوشان برای سخنرانی‌ها رو انتخاب میکنیم اینجا هم همین کار رو میکنیم زیرا اعضای این مجموعه میتونن تو یک کلاس بر گزار بشن حالا اینا رو از مجموعه اصلی حذف میکنیم و دوباره بین باقی مونده‌ها باز حداکثر رو پیدا میکنیم به همین ترتیب تا مجموعه خالی بشه.
نظرتون چیه؟؟؟؟
هر بار اجرای الگوریتم برای یافتن حداکثر مجموعه‌ی غیر هم پوشان O(N) اگر فرض کنیم همه N محموعه همپوشانی داشته باشند مجبوربم N بار الگوریتم را تا رسیدن به محموعه خالی تکرار کنیم که میشه N^2
کسی راه حل دیگری ندارد لطفا جواب بدید
intervall treeبخش ۱۴/۳ کتاب CLRS
تو تمریناش مثل همین سوال است point of max overlap
ساخت یک درخت قرمز-سیاه با yها با مرتبه nlogn
سپس قرار دادن اطلاعات x در هر گره
پیچیدگی زمانیش هم کلا nlogn
(۰۶ بهمن ۱۳۹۰ ۰۱:۲۱ ق.ظ)reza_dev نوشته شده توسط: intervall treeبخش ۱۴/۳ کتاب CLRSممنون از چوابتان می شود کاملتر توضیح دهید
تو تمریناش مثل همین سوال است point of max overlap
ساخت یک درخت قرمز-سیاه با yها با مرتبه nlogn
سپس قرار دادن اطلاعات x در هر گره
پیچیدگی زمانیش هم کلا nlogn
چیزی که تو کتاب طراحی الگوریتم پارسه به عنوان راه حلش توضیح داده اینجوریه که:
ما ابتدا تمام داده‌ها بر حسب صعودی مرتب می کنیم یعنی تو یک مجموعه هم زمان شروع و هم زمان پایان رو داریم که به ترتیب صعودی هستن
دو پشته در نظر میگیریم: یکی برای کلاس های پر و دیگری برای کلاس های خالی
مجموعه را پیمایش میکنیم اگر به یک زمان شروع رسیدیم، یک کلاس از پشته‌ی کلاس های خالی pop کرده و در پشته‌ی کلاس های خالی push میکنیم
و اگر به زمان پایان رسیدیم، بر عکس عمل میکینم و یک کلاس از پشته‌ی پر بر میداریم و در پشته‌ی خالی میگذاریم
تعداد کلاس هایی که در پشته‌ی کلاس های پر قرار میدهیم برابر کمترین تعداد کلاس هاست
و چون زمان push و pop حداکثر میشه [tex]O(n)[/tex] پس زمان کل برابر با همون زمان مرتب سازی میشه یعنی:
[tex]O(nlogn)[/tex]
ممنون از جوابتان
ییخشید که گیجم ممکن این سوال را با این متال حل کنید
(۱و۳)
(۲و۴)
(۵و۶)
(۷و۱۰)
(۸و۹)
اینکه کفتید داده‌ها را مرتب کردید منظورتان این هست اول بر اساس زمان شروع بعد بر اساس زمان پایان مرتب می کنید؟
(۰۶ بهمن ۱۳۹۰ ۰۷:۴۲ ب.ظ)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 میکنی .
حداکثر کلاس هایی که داخل پشته گذاشتی میشه حداقل کلاس ها
تو این مثال پشته حدا کثر به اندازه ۲ پر میشه.
حالا ممکنه بعضی وقتها خالی بشه یا اینکه فقط یکی تو پشته باشه اما مهم اینه که یک بار ما ۲ تا کلاس تو پشته داشتیم.