انتخاب فعالیت‌ها
بیشترین تعداد فعالیت بدون هم‌پوشانی را انتخاب می‌کند: همیشه فعالیتی که زودتر تمام می‌شود، اگر با قبلی تداخل نداشته باشد.
چند فعالیت (مثلاً کلاس‌ها در یک سالن) با زمان شروع s و پایان f داریم و می‌خواهیم بیشترین تعداد را بدون هم‌پوشانی انتخاب کنیم.
- زمان:
O(n log n) - حافظه:
O(n) - CLRS، بخش ۱۵.۱
یازده فعالیت؛ چهار تا انتخاب می‌شوند: ۱ تا ۴، ۵ تا ۷، ۸ تا ۱۱ و ۱۲ تا ۱۶.
def activity_selection(activities):# Each activity is [start, finish); take them in order of finishing time.acts = sorted(activities, key=lambda a: a[1])chosen = []free_from = 0for start, finish in acts:if start >= free_from:chosen.append([start, finish])free_from = finishreturn len(chosen)
شروع اجرا
acts
جدول هنوز خالی است.
chosen
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
activities list
Call stack
- activity_selection()خط 1
توضیح
ایده
چند فعالیت (مثلاً کلاس‌ها در یک سالن) با زمان شروع s و پایان f داریم و می‌خواهیم بیشترین تعداد را بدون هم‌پوشانی انتخاب کنیم.
انتخاب حریصانه: فعالیت‌ها را بر اساس زمان پایان مرتب کن و هر فعالیتی را که بعد از آخرین فعالیت انتخاب‌شده شروع می‌شود بردار.
چرا درست است؟
فعالیتی که زودتر از همه تمام می‌شود، بیشترین زمان را برای بقیه باقی می‌گذارد. اگر یک جواب بهینه با آن شروع نشود، می‌شود اولین فعالیتش را با این یکی عوض کرد و هنوز تداخلی پیش نمی‌آید؛ پس انتخاب حریصانه همیشه در یک جواب بهینه هست.
انتخاب بر اساس زودترین شروع یا کوتاه‌ترین مدت همیشه درست کار نمی‌کند (ورودی «طولانی‌ترین اول» را ببین).
در trace به چه چیزی نگاه کنی
- جدول
actsفعالیت‌های مرتب‌شده و جدولchosenانتخاب‌هاست؛free_fromلحظه‌ای است که سالن آزاد می‌شود.