Job Sequencing Problem

Q: מהי סיבוכיות הזמן של בעיית תזמון העבודות?

עם קבוצת זרות, זמן הריצה הוא O(n log n) , והוא נשלט על ידי המיון, ונדרש מקום בנפח O(n) . סריקה לאחור מכל מועד אחרון כדי למצוא משבצת פנויה עולה O(n²) כאשר רוב המועדים האחרונים גדולים.

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

+10

מקבלים n עבודות כשני מערכים: עבודה i מניבה profit[i] אם היא מסתיימת עד למועד האחרון deadline[i]. כל עבודה נמשכת יחידת זמן אחת, מבצעים עבודה אחת בכל פעם החל בזמן 0, ואפשר לדלג על כל עבודה. אפשר לבצע עבודה עם מועד אחרון 2 בין 0 ל־1 או בין 1 ל־2.

החזירו את הרווח הכולל המרבי שאפשר להרוויח.

פונקציה

jobSequencing(deadline: integer-array, profit: integer-array) → integer

deadlineinteger-array: הזמן שבו כל משימה צריכה להסתיים, מ־1 עד n
profitinteger-array: מה כל עבודה מרוויחה; profit[i] שייך ל-deadline[i]
מחזירהinteger: הרווח הכולל הגדול ביותר של העבודות שיכולות להסתיים כולן עד מועדי היעד שלהן

אילוצים

1 ≤ deadline.length == profit.length ≤ 5000
1 ≤ deadline[i] ≤ n, כאשר n הוא מספר המשימות
1 ≤ profit[i] ≤ 10⁵
המערכים אינם ממוינים. לכמה משימות עשויים להיות אותו מועד אחרון או אותו רווח.

דוגמאות

קלט: deadline = [3, 1, 2, 3, 1]profit = [40, 35, 30, 25, 50]
פלט: 120
הסבר: רק אחת משתי העבודות עם מועד אחרון 1 מתאימה, לכן בצע את זו ששווה 50. העבודה ששווה 30 מסתיימת אז במועד האחרון שלה, 2, והעבודה ששווה 40 במועד האחרון שלה, 3: 50 + 30 + 40 = 120.

קלט: deadline = [1, 1, 1]profit = [5, 9, 7]
פלט: 9
הסבר: כל שלוש העבודות צריכות להסתיים עד זמן 1, ורק עבודה אחת יכולה להתבצע לפני כן. הטובה ביותר מביניהן מזכה ב-9.

שאלת המשך

מה אם ביצוע משימה i אורך duration[i] יחידות זמן במקום יחידה אחת? האם בחירת המשימה הרווחית ביותר תחילה עדיין תיתן את הרווח הכולל הטוב ביותר?

פתרון

אתה בוחר אילו עבודות לשמור ומתי להריץ אותן. כלל חמדני אחד קובע את שניהם: קח את העבודות מהמשתלמת ביותר ומטה, ושבץ כל אחת במשבצת הפנויה המאוחרת ביותר עד למועד האחרון שלה, ודלג עליה אם אין משבצת פנויה. מבנה נתונים של קבוצות זרות מוצא את המשבצת הזאת בלי לעבור על משבצות שכבר הוזמנו.

חמדני לפי רווח, תוך סריקה לאיתור משבצת פנויה

האינטואיציה

חלקו את הזמן למשבצות: משבצת t נמשכת מ־t-1 עד t, משימה עם מועד אחרון d יכולה להשתמש במשבצות 1 עד d, ואף מועד אחרון אינו עולה על n. בטוח לבחור תחילה את המשימה הרווחית ביותר: אם כל המשבצות שבהן היא יכולה להשתמש תפוסות, החלפתה במשימה שבאחת מהן תניב לפחות אותו רווח. בטוח לשבץ במשבצת המאוחרת ביותר, כי רק משימות עם מועדים אחרונים מוקדמים יכולות להשתמש במשבצות המוקדמות.

העלות היא הסריקה. כאשר כל המועדים האחרונים הם n, המשימה ה־k עוברת על פני k-1 משבצות תפוסות: בערך n²/2, או 12.5 מיליון צעדים כאשר n = 5000.

אלגוריתם

מיין את העבודות לפי רווח, מהגדול לקטן, ושמור את המועד האחרון של כל עבודה יחד עם הרווח שלה.
צור מערך taken של n + 1 דגלים, שכולם false.
עבור כל עבודה, עבור מ-t כלפי מטה, החל מהמועד האחרון שלה ועד 1, ועצור במשבצת הראשונה שאינה תפוסה.
אם מצאת משבצת כזו, סמן אותה כתפוסה והוסף את רווח העבודה ל-total.
החזר את total.

def jobSequencing(deadline, profit):
    n = len(deadline)
    taken = [False] * (n + 1)  # taken[t]: the time unit from t-1 to t is booked
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        for t in range(deadline[i], 0, -1):  # latest free slot first
            if not taken[t]:
                taken[t] = True
                total += profit[i]
                break
    return total

בחירה חמדנית לפי הרווח באמצעות קבוצת משבצות פנויות זרות בזוגות

האינטואיציה

הסריקה עוברת שוב ושוב על אותם משבצות זמן שהוזמנו. מבנה קבוצות זרות על המשבצות מ־0 עד n מדלג עליהן: parent[t] = t כל עוד משבצת הזמן t פנויה, והזמנתה קובעת parent[t] = t-1, כך שמעקב אחר המצביעים מתאריך יעד מוביל למשבצת הזמן הפנויה האחרונה. הגעה למשבצת הזמן 0 פירושה שלא נותר דבר. קיצור מסלולים מצביע מכל משבצת זמן שעוברים עליה שתי משבצות קדימה, כך שמעברים מאוחרים יותר יהיו קצרים יותר.

בדוגמה השלישית, העבודות ששוות 60 ו־50 תופסות את משבצות הזמן 2 ו־1. העבודה ששווה 20, עם תאריך יעד 2, עוקבת מ־2 אל 1 ואז אל 0, ולכן מדלגים עליה.

המיון עולה O(n log n), ועם קיצור מסלולים כל חיפוש עולה O(log n) בממוצע אמורטי, כך שהעלות הכוללת נשארת O(n log n).

אלגוריתם

מיינו את העבודות לפי רווח, מהגדול לקטן, תוך שמירה על כל מועד אחרון לצד הרווח שלו.
הגדירו parent[t] = t עבור כל משבצת t מ-0 עד n.
עבור כל עבודה, התחילו ב-slot = deadline והמשיכו לעקוב אחר parent עד ש-parent[slot] == slot, תוך כדי חציית הנתיב.
אם slot > 0, הוסיפו את הרווח של העבודה והגדירו parent[slot] = slot-1; אחרת דלגו על העבודה.
החזירו את הסכום הכולל.

def jobSequencing(deadline, profit):
    n = len(deadline)
    # following parent from slot t ends at the latest free slot at or before t; 0 means none is left
    parent = list(range(n + 1))
    total = 0
    for i in sorted(range(n), key=lambda i: profit[i], reverse=True):  # most profitable first
        slot = deadline[i]
        while parent[slot] != slot:
            parent[slot] = parent[parent[slot]]  # halve the path as you go
            slot = parent[slot]
        if slot > 0:
            total += profit[i]
            parent[slot] = slot - 1  # booked: its chain continues at the slot before it
    return total

מלכודות ומקרי קצה

הכנסת משימה למשבצת הפנויה המוקדמת ביותר. בדוגמה השלישית, המשימה ששווה 60 תתפוס את משבצת 1, והמשימה ששווה 50 תלך לאיבוד: 80 במקום 110.
בחירת משימות לפי סדר המועד האחרון. עם מועדים אחרונים [1, 1] ורווחים [1, 100], המשימה הזולה תתפוס את המשבצת היחידה ותרוויח 1 במקום 100.
הגדרת גודל מערך המשבצות כ-n במקום n + 1. מועד אחרון ששווה ל-n יגרום לקריאה מעבר לסוף המערך.
מיון הרווחים לבדם. כל מועד אחרון חייב לנוע יחד עם הרווח שלו.
כתיבת שלב החיפוש באמצעות רקורסיה. שרשרת שעוברת דרך אלפי משבצות תפוסות עלולה לגרום לגלישת מחסנית; השתמשו בלולאה.

שאלות נפוצות3

מהי סיבוכיות הזמן של בעיית תזמון העבודות?

עם קבוצת זרות, זמן הריצה הוא O(n log n), והוא נשלט על ידי המיון, ונדרש מקום בנפח O(n). סריקה לאחור מכל מועד אחרון כדי למצוא משבצת פנויה עולה O(n²) כאשר רוב המועדים האחרונים גדולים.

למה הגישה החמדנית עובדת בתזמון משימות?

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

האם אפשר לפתור את בעיית תזמון העבודות באמצעות ערימה במקום זאת?

כן. מיין את העבודות לפי מועד אחרון והכנס כל רווח לערימת מינימום. בכל פעם שהערימה מכילה יותר עבודות מכפי שמועד אחרון הנוכחי מאפשר, הוצא ממנה את הרווח הקטן ביותר. בסוף הערימה מכילה את קבוצת העבודות הטובה ביותר, והסכום שלה הוא התשובה, ב־O(n log n).

def jobSequencing(deadline, profit):
    # כתבו כאן קוד

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

deadline = [3, 1, 2, 3, 1]
profit = [40, 35, 30, 25, 50]

הפלט הצפוי