Task Scheduler

Q: מהי סיבוכיות הזמן של Task Scheduler?

ספירת האותיות אורכת O(m) עבור m משימות, ואז הנוסחה קוראת 26 ספירות, כך שהפתרון דורש זמן O(m) וזיכרון נוסף O(1) . סימולציית ערימת המקסימום מוציאה איבר פעם אחת לכל משימה, כלומר O(m log k) כאשר k ≤ 26 אותיות.

Q: מתי מתזמן המשימות לא זקוק לזמן סרק?

כאשר m ≥ (top-1) × (n+1) + atTop , המשימות ממלאות כל משבצת פנויה ומאריכות את מסגרות הזמן במקום להשאיר פערים, ולכן התשובה היא m . דוגמה 2, "ABCABD" עם n = 1 , היא מקרה כזה.

בינוניאלגוריתם חמדן ערימה גיבוב

+10

ניתנת לך מחרוזת של אותיות גדולות באנגלית בשם tasks, אות אחת לכל משימה, ומספר שלם n. מעבד מריץ משימה אחת בכל יחידת זמן, בכל סדר שתבחר, או נשאר במצב המתנה במשך יחידה אחת.

בין שתי הרצות של אותה אות צריכות להיות לפחות n יחידות זמן: אות שהורצה ביחידה t יכולה לרוץ שוב לכל המוקדם ביחידה t+n+1. החזר את מספר יחידות הזמן הקטן ביותר הדרוש להרצת כל המשימות.

פונקציה

leastInterval(tasks: string, n: integer) → integer

tasksstring: המשימות, אות גדולה אחת לכל משימה
ninteger: המספר הקטן ביותר של יחידות בין שתי הופעות של אותה אות
מחזירהinteger: מספר היחידות הקטן ביותר, כולל יחידות סרק

אילוצים

1 ≤ tasks.length ≤ 10⁴
tasks מכיל רק את האותיות הגדולות 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 יחידות.

שאלת המשך

האם תוכל גם להחזיר לוח זמנים אחד באורך הקצר ביותר, כמחרוזת עם . עבור כל יחידת זמן פנויה?

רמזים

פתחו אותם אחד אחד. כל רמז חושף קצת יותר.

נפתחו 0 מתוך 3

פתרון

את/ה בוחר/ת את הסדר, ולכן השאלה היא כמה יחידות סרק מעטות נדרשות. האות הנפוצה ביותר קובעת: המופעים שלה חייבים להיות במרווח של 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

מהי סיבוכיות הזמן של Task Scheduler?

ספירת האותיות אורכת 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 דורשים שניהם 7 יחידות.

def leastInterval(tasks, n):
    # כתבו כאן את הקוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

tasks = "CACBAC"
n = 2

הפלט הצפוי