Task Scheduler
لديك سلسلة نصية tasks تتكون من أحرف كبيرة، حيث يمثل كل حرف مهمة، وعدد صحيح n. ينفذ المعالج مهمة واحدة في كل وحدة زمنية، بأي ترتيب تختاره، أو يبقى خاملاً لوحدة زمنية.
يجب أن تفصل بين تنفيذين للحرف نفسه n وحدات على الأقل: إذا نُفّذ حرف في الوحدة t، فيمكن تنفيذه مجددًا في أقرب وقت في الوحدة t+n+1. أعد أقل عدد من الوحدات اللازمة لتنفيذ كل المهام.
الدالة
- tasksstring
- المهام، حرف كبير واحد لكل منها
- ninteger
- أقل عدد من الوحدات بين تكرارين للحرف نفسه
- تُرجعinteger
- أقل عدد من الوحدات، بما فيها الوحدات الخاملة
القيود
1 ≤ tasks.length ≤ 104tasksيحتوي على الأحرف الكبيرة فقط منAإلىZ.0 ≤ n ≤ 100
أمثلة
- المدخلات
- tasks = "CACBAC"n = 2
- المخرجات
- 7
- الشرح
- تعمل C ثلاث مرات مع وحدتين بين مرات التشغيل، لذا تمتد مرات تشغيلها وحدها على 7 وحدات. يملأ الترتيب
C A B C A، ثم الخمول، ثمCالفجواتَ بـ A وB ويحتاج إلى وحدة خمول واحدة:7.
- المدخلات
- tasks = "ABCABD"n = 1
- المخرجات
- 6
- الشرح
- يُنفَّذ كلٌّ من A وB مرتين، مع وحدة واحدة بين التنفيذين. يُبقيهما الترتيب
A B C A B Dمتباعدين من دون أي وحدة خمول، لذا فالإجابة هي عدد المهام،6.
- المدخلات
- tasks = "ZZZ"n = 3
- المخرجات
- 9
- الشرح
- لا يوجد سوى Z للتنفيذ، لذا فإن كل فجوة خاملة: Z، ثلاث وحدات خاملة، Z، ثلاث وحدات خاملة، Z. هذا يساوي
9وحدات.
سؤال إضافي
هل يمكنك أيضًا إرجاع جدول واحد بأقل طول، كسلسلة تحتوي على . لكل وحدة خمول؟
تلميحات
افتحها واحدًا تلو الآخر. كل تلميح يكشف أكثر قليلًا.
أي حرف يجعل وقت الخمول أمرًا لا مفر منه؟ فكّر في الحرف الأكثر تكرارًا ومدى التباعد الذي يجب أن تكون عليه مرات ظهوره المتتالية.
رتّب الحرف الأكثر تكرارًا أولًا: مجموعة واحدة، و
nخانات مفتوحة، ثم مجموعة أخرى، وهكذا. كم وحدة يتطلب ذلك، وما الذي يمكن وضعه في الخانات المفتوحة؟باعتبار
topأعلى عدد، وatTopعدد الحروف التي لها هذا العدد، تشغل الإطارات(top-1) × (n+1) + atTopوحدة. قارن ذلك بعدد المهام.
الحل
أنت تختار الترتيب، لذا فالسؤال هو: ما أقل عدد من الوحدات الخاملة التي تحتاج إليها؟ الحرف الأكثر تكرارًا هو ما يحدد ذلك: يجب أن تفصل n+1 وحدة بين مرات ظهوره، وتملأ المهام الأخرى الفجوات بينها. نفّذ الحروف الأكثر تكرارًا أولًا باستخدام كومة عظمى، أو احسب الفجوات مباشرةً باستخدام صيغة واحدة.
محاكاة الجولات باستخدام كومة عظمى
الفكرة
قسّم الوقت إلى جولات، مدة كل منها n+1 وحدة. لا يجوز تشغيل الحرف نفسه مرتين في الجولة، ويمكن تشغيل حرف في خانة معيّنة من إحدى الجولات مرة أخرى في الخانة نفسها من الجولة التالية، بعد n+1 وحدة بالضبط. في كل جولة، شغّل الأحرف التي لديها أكبر عدد من النسخ المتبقية. يجب أن تفصل بين مرات تشغيلها المتبقية n+1 وحدة، لذا فهي الأحرف التي قد تفرض وقت خمول في النهاية؛ وتشغيلها أولًا يُبقي الأعداد متقاربة.
تكلف الجولة التي يبقى بعدها عمل n+1 وحدة، تكون خاناتها الفارغة وقت خمول؛ أما الجولة الأخيرة فلا تكلف سوى مدة المهام التي شغّلتها. في المثال 1، تشغّل الجولات C A B، ثم C A ووحدة خمول واحدة، ثم C الأخيرة: 3 + 3 + 1 = 7. كل عملية إخراج من الكومة تشغّل مهمة واحدة، لذا مع m مهمة وk ≤ 26 حرفًا، يكون التعقيد O(m log k).
الخوارزمية
- احسب عدد مرات ظهور كل حرف وضع الأعداد التي تزيد على الصفر في كومة عظمى.
- ما دامت الكومة غير فارغة، نفّذ جولة: أخرج ما يصل إلى
n+1من الأعداد، واحتفظ بكل عدد بعد طرح واحد منه إذا ظل أكبر من الصفر. - أعِد الأعداد التي احتفظت بها إلى الكومة.
- أضف
n+1إلى الوقت إذا لم تكن الكومة فارغة؛ وإلا فأضف عدد المهام التي نُفّذت في الجولة. - أعِد الوقت.
import heapq
from collections import Counter
def leastInterval(tasks, n):
# heapq is a min-heap, so store negated counts to pop the largest first.
heap = [-c for c in Counter(tasks).values()]
heapq.heapify(heap)
time = 0
while heap:
# One round of n+1 slots: run the most frequent tasks left, each at most once.
left = []
ran = 0
while ran < n + 1 and heap:
c = -heapq.heappop(heap)
ran += 1
if c > 1:
left.append(c - 1)
for c in left:
heapq.heappush(heap, -c)
# A round lasts n+1 units, idle included; the last one ends with its last task.
time += n + 1 if heap else ran
return timeاحسب عدد إطارات الحرف الأكثر تكرارًا
الفكرة
لتكن top أعلى عدد، وتحمله الحرف X. رتّب X مع n خانات مفتوحة بعد كل مجموعة، ما عدا الأخيرة: top-1 إطارًا، طول كل منها n+1 وحدة، ثم مجموعة X الأخيرة. يمكن وضع حرف يتكرر أقل من top مرة في الخانات المفتوحة، نسخة واحدة في كل إطار، لذا تبقى نسخة كل حرف على بُعد لا يقل عن n+1 من النسخة التالية. ويضيف كل حرف آخر يتكرر top مرة وحدة واحدة في النهاية. وبوجود atTop من الأحرف التي لها أعلى عدد من التكرارات، يكون المجموع (top-1) × (n+1) + atTop وحدة.
لا يمكن أن يكون أي جدول أقصر: قسّم أول (top-1) × (n+1) وحدة إلى top-1 نافذة، طول كل منها n+1. يظهر كل حرف ذي أعلى عدد من التكرارات مرة واحدة على الأكثر في كل نافذة، لذا تظل لكل واحد من الأحرف الـatTop مجموعة واحدة بعد النوافذ. إذا كان عدد المهام أكبر من عدد الخانات المفتوحة، فلتتجاوز بعض الإطارات n+1 وحدة. الإطار الأطول لا يؤدي إلا إلى توسيع الفواصل، لذا لا توجد أي فترة خمول، وتكون الإجابة m. الإجابة هي الأكبر من القيمتين.
الخوارزمية
- احسب عدد مرات ظهور كل حرف من الأحرف الـ26.
- أوجد
top، وهو أعلى عدد، وatTop، وهو عدد الأحرف التي ظهر فيها بهذا العدد. - احسب
frames = (top-1) × (n+1) + atTop. - أعِد الأكبر من
framesوعدد المهام.
def leastInterval(tasks, n):
counts = [0] * 26
for ch in tasks:
counts[ord(ch) - ord("A")] += 1
top = max(counts)
at_top = counts.count(top) # tasks that share the highest count
# top-1 full frames of n+1 units, then one last slot per task at the top count.
frames = (top - 1) * (n + 1) + at_top
# With more tasks than frame slots, no idle unit is needed at all.
return max(frames, len(tasks))
أخطاء شائعة وحالات حدّية
- نسيان الأحرف المتعادلة في الصدارة. في
"MMNNPP"معn = 5، عدد مرات ظهور الأحرف الثلاثة هو 2، لذا الإجابة هي(2-1) × 6 + 3 = 9، وليست 7. - نسيان خطوة أخذ الأكبر. في المثال 2، تعطي الإطارات
(2-1) × 2 + 2 = 4، لكن ست مهام تحتاج إلى ست وحدات. - احتساب
n+1وحدة كاملة للجولة الأخيرة. لا يوجد انتظار بعد المهمة الأخيرة: ستكون نتيجة المثال 3 هي 12 بدلًا من 9. - إعادة عددٍ إلى داخل الجولة. عندئذٍ يمكن إخراج الحرف نفسه مرة أخرى في تلك الجولة وتشغيله مرتين بفاصل قصير جدًا.
أسئلة شائعة3
ما هو التعقيد الزمني لجدولة المهام؟
يستغرق عدّ الأحرف O(m) عند وجود m من المهام، ثم تقرأ الصيغة 26 عددًا، لذا يستغرق الحل O(m) من الوقت وO(1) من الذاكرة الإضافية. تحاكي طريقة الكومة ذات الأولوية القصوى عملية الإزالة مرة واحدة لكل مهمة، بتعقيد O(m log k)، حيث k ≤ 26 حرفًا.
متى لا يحتاج «مُجدوِل المهام» إلى وقت خمول؟
عندما m ≥ (top-1) × (n+1) + atTop، تملأ المهام كل خانة مفتوحة وتُمدِّد الإطارات بدلًا من ترك فجوات، لذا تكون الإجابة m. المثال 2، "ABCABD" مع n = 1، حالة من هذا النوع.
هل يهم ترتيب سلسلة الإدخال؟
لا. أنت تختار ترتيب تنفيذ المعالج للمهام، لذا المهم هو عدد مرات ظهور كل حرف فقط. يتطلب كلٌّ من "CACBAC" و"CCCAAB" مع n = 2 سبع وحدات.
مسائل مشابهة
مسائل تعتمد على الأفكار نفسها. حلّ اثنتين أو ثلاث منها يثبّت النمط.
def leastInterval(tasks, n):
# اكتب الكود هنااختبار #1
اختبار #2
اختبار #3
الوسائط
tasks = "CACBAC" n = 2
الإخراج المتوقع
7