Activity Selection Problem

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

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

Q: מהי בעיית N הפגישות בחדר אחד?

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

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

+10

פעילות i נמשכת מהזמן start[i] עד הזמן finish[i]. אדם אחד מבצע פעילות אחת בכל פעם, והפעילות הבאה חייבת להתחיל רק לאחר שהפעילות הקודמת מסתיימת: פעילות שמתחילה בדיוק בזמן שבו פעילות אחרת מסתיימת אינה יכולה לבוא אחריה.

החזירו את המספר המרבי של פעילויות שאדם אחד יכול לבצע.

פונקציה

maxActivities(start: integer-array, finish: integer-array) → integer

startinteger-array: שעת ההתחלה של כל פעילות
finishinteger-array: זמן הסיום של כל פעילות; finish[i] שייך ל-start[i]
מחזירהinteger: מספר הפעילויות המרבי שאדם אחד יכול לבצע, בזו אחר זו

אילוצים

1 ≤ start.length == finish.length ≤ 5000
0 ≤ start[i] ≤ finish[i] ≤ 10⁵
פעילות עשויה להתחיל ולהסתיים באותו זמן. המערכים אינם ממוינים.

דוגמאות

קלט: 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 הוא שקר.

שאלות נפוצות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]

הפלט הצפוי