Activity Selection Problem
يمتد النشاط i من الوقت start[i] إلى الوقت finish[i]. ينفّذ شخص واحد نشاطًا واحدًا في كل مرة، ويجب أن يبدأ النشاط التالي بعد انتهاء النشاط السابق تمامًا: لا يمكن أن يتبع النشاطَ نشاطٌ يبدأ في الوقت نفسه الذي ينتهي فيه نشاط آخر.
أعِد أكبر عدد من الأنشطة التي يمكن لشخص واحد تنفيذها.
الدالة
- startinteger-array
- وقت بدء كل نشاط
- finishinteger-array
- وقت انتهاء كل نشاط؛ finish[i] يقابل start[i]
- تُرجعinteger
- أكبر عدد من الأنشطة التي يمكن لشخص واحد القيام بها، واحدًا تلو الآخر
القيود
1 ≤ start.length == finish.length ≤ 50000 ≤ start[i] ≤ finish[i] ≤ 105- قد يبدأ نشاط وينتهي في الوقت نفسه. المصفوفات غير مرتبة.
أمثلة
- المدخلات
- start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
- المخرجات
- 4
- الشرح
- تنفيذ 10 إلى 13، و14 إلى 19، و21 إلى 22، و25 إلى 30 يعطي 4. خمسة مستحيلة: 10 إلى 13 تتعارض مع 12 إلى 16، و21 إلى 22 مع 20 إلى 24.
- المدخلات
- start = [1, 5, 9]finish = [5, 9, 12]
- المخرجات
- 2
- الشرح
- يبدأ النشاط من 5 إلى 9 في الوقت نفسه تمامًا الذي ينتهي فيه النشاط الأول، لذا لا يمكن أن يأتي بعده. ينجح تنفيذ النشاط من 1 إلى 5 ثم من 9 إلى 12، لذا فالإجابة هي
2.
- المدخلات
- start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
- المخرجات
- 3
- الشرح
- يتداخل النشاط من 0 إلى 100 مع جميع الأنشطة الأخرى. عند استبعاده، تتتابع الفترات من 2 إلى 4، ومن 5 إلى 7، ومن 8 إلى 10:
3.
سؤال إضافي
يعمل شخصان الآن بالتوازي، وينفّذ كلٌّ منهما نشاطًا واحدًا في كل مرة. كم نشاطًا يمكنهما إنجازه معًا، ومن الشخص الذي ينبغي أن يتولى كل نشاط؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
افترض أنك تعرف بالفعل النشاط الذي ستقوم به أولًا. أي نشاط تريده أن يكون، بحيث يتبقى بعده أكبر قدر ممكن من الوقت؟
النشاط الذي ينتهي أولًا هو دائمًا خيار أول آمن: يمكن لخطة تبدأ بأي نشاط آخر أن تستبدله بالنشاط الذي ينتهي أولًا وتحافظ على العدد نفسه. بعد ذلك، يتكرر السؤال نفسه بشأن الأنشطة التي تبدأ بعد انتهائه.
رتّب الأنشطة حسب وقت الانتهاء، مع نقل وقت بدء كل نشاط مع وقت انتهائه. تجوّل في القائمة المرتبة مع الاحتفاظ بوقت انتهاء آخر نشاط اخترته، واختر كل نشاط يكون وقت بدئه أكبر من ذلك الوقت بشكل صارم.
الحل
يستغرق فحص كل مجموعة جزئية من الأنشطة وقتًا أُسّيًا. لكن قاعدة جشعة واحدة تحسم المسألة: من بين الأنشطة التي لا يزال بإمكانك إدراجها، اختر دائمًا النشاط الذي ينتهي أولًا. ويحوّل الترتيب حسب وقت الانتهاء هذه القاعدة إلى مرور واحد.
اختر وقت الانتهاء الأقرب، مرة بعد مرة
صحيحة، لكنها لا تنتهي في أكبر الاختبارات
الفكرة
النشاط الذي ينتهي أبكر من جميع الأنشطة الأخرى يكون اختيارًا أوليًا جيدًا على الأقل بقدر أي نشاط آخر. فهو لا يحررك في وقت لاحق، لذا فإن أي نشاط يمكن أن يأتي بعد اختيار أولي آخر يمكن أن يأتي بعده أيضًا، واستبداله به يحافظ على العدد. بعد هذا الاختيار، تتكرر المسألة مع الأنشطة التي تبدأ بعد انتهائه.
في المثال الأول تختار من 10 إلى 13، ثم من 14 إلى 19، ثم من 21 إلى 22، ثم من 25 إلى 30: أربعة أنشطة.
يمسح كل اختيار جميع الأنشطة البالغ عددها n، لذا فإن الكلفة تساوي n مضروبًا في الإجابة. عندما تتسع الفترات الزمنية لجميع الأنشطة البالغ عددها 5000 نشاطًا لتأتي الواحدة بعد الأخرى، يكون العدد 25 مليون عملية تحقق.
الخوارزمية
- عيّن
count = 0وlastFinish = -1، بعد جميع أوقات البدء. - افحص جميع الأنشطة للعثور على النشاط الذي يحقق
start[i] > lastFinishوينتهي أولًا. - إذا لم يوجد، فأعِد
count. - وإلا، أضف 1 إلى
count، وعيّنlastFinishإلى وقت انتهاء ذلك النشاط، ثم افحص مرة أخرى.
def maxActivities(start, finish):
n = len(start)
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
while True:
# among the activities that start after last_finish, find the one that ends first
pick = -1
for i in range(n):
if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
pick = i
if pick == -1:
return count
count += 1
last_finish = finish[pick]رتّب حسب وقت الانتهاء واختر بشكل جشع
الفكرة
رتّب الأنشطة حسب وقت الانتهاء مرة واحدة، وستصادف الأنشطة بالترتيب الذي بحثت عنها به عمليات المسح أعلاه. تجوّل في القائمة المرتبة محتفظًا بـ lastFinish، وهو وقت انتهاء آخر نشاط اخترته. النشاط الذي يحقق start[i] > lastFinish هو أقرب نشاط انتهاءً لا يزال مناسبًا، لذا اختره. أما أي نشاط آخر فيتعارض مع آخر اختيار لك، لذا فإن تخطيه لا يكلّفك شيئًا.
بعد الترتيب، يصبح المثال الأول: من 10 إلى 13، ومن 12 إلى 16، ومن 14 إلى 19، ومن 21 إلى 22، ومن 20 إلى 24، ومن 25 إلى 30. اختر الأول والثالث والرابع والسادس: فالوقت 12 ليس بعد 13، والوقت 20 ليس بعد 22.
لا حاجة إلى قاعدة لحسم التعادل في وقت الانتهاء. ما إن تختار نشاطًا ينتهي عند t، حتى يكون وقت بدء كل نشاط آخر ينتهي عند t مساويًا لـ t أو قبله، وبالتالي يُتخطّى.
الخوارزمية
- رتّب الأنشطة حسب
finish، مع نقل وقت بدء كل نشاط مع وقت انتهائه. - عيّن
count = 0وlastFinish = -1. - لكل نشاط بهذا الترتيب، إذا كان
start[i] > lastFinish، فأضف 1 إلىcountوعيّنlastFinish = finish[i]. - أعِد
count.
def maxActivities(start, finish):
order = sorted(range(len(start)), key=lambda i: finish[i]) # earliest finish first
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
for i in order:
if start[i] > last_finish:
count += 1
last_finish = finish[i]
return count
أخطاء شائعة وحالات حدّية
- الترتيب حسب وقت البدء. في المثال الثالث، يبدأ النشاط من 0 إلى 100 أولًا ويمنع الأنشطة الثلاثة الأخرى.
- اختيار أقصر نشاط أولًا. مع الأنشطة من 1 إلى 5، ومن 5 إلى 6، ومن 6 إلى 10، يكون الأقصر هو من 5 إلى 6، وهو يتعارض مع النشاطين الآخرين؛ ويعطي النشاطان من 1 إلى 5 ومن 6 إلى 10 العدد 2.
- المقارنة باستخدام
≥بدلًا من>. في المثال الثاني، يعيد ذلك 3 بدلًا من 2. - ترتيب
finishوحده. يجب أن يتحرك كل وقت بدء مع وقت انتهائه الخاص، وإلا فستقترن أوقات البدء بالأنشطة الخاطئة. - بدء
lastFinishبالقيمة 0. عندئذٍ يتم تخطي نشاط وحيد من 0 إلى 1، لأن0 > 0تكون نتيجته false.
أسئلة شائعة3
ما التعقيد الزمني لمشكلة اختيار الأنشطة؟
يستغرق الترتيب حسب وقت الانتهاء O(n log n)، وتستغرق المرحلة الجشعة بعده O(n)، لذا فإن الترتيب هو العامل المسيطر. إذا كانت الأنشطة مرتبة مسبقًا حسب وقت الانتهاء، فإن هذه المرحلة وحدها تحل المسألة في زمن O(n) ومساحة إضافية O(1).
ما هي مسألة N اجتماعات في غرفة واحدة؟
إنها المشكلة نفسها، لكن بصياغة تتعلق بالاجتماعات: غرفة واحدة، وN اجتماعًا، ولا يمكن أن يبدأ اجتماع إلا بعد انتهاء الاجتماع السابق. رتّب الاجتماعات حسب وقت انتهائها، واختر كل اجتماع يبدأ بعد انتهاء آخر اجتماع اخترته. ولإدراج الاجتماعات، سجّل فهرس كل اجتماع تختاره، وعند تعادل أوقات الانتهاء اختر الاجتماع ذا الفهرس الأصغر.
هل تُعدّ مسألة اختيار الأنشطة برمجةً ديناميكية؟
يمكن ذلك، لكنه ليس ضروريًا. جدول للأنشطة المرتبة حسب وقت الانتهاء، يحتفظ بأكبر عدد من الأنشطة المنتهية عند كل نشاط، يعطي الإجابة في O(n²). يكون الاختيار الجشع آمنًا دائمًا، لذا تكفي عملية مرور واحدة. يصبح الجدول الأداة المناسبة عندما تكون للأنشطة قيم وتريد تعظيم مجموعها.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def maxActivities(start, finish):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
start = [10, 12, 20, 14, 25, 21] finish = [13, 16, 24, 19, 30, 22]
الإخراج المتوقع
4