Non-overlapping Intervals

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

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

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

+10

נתונה לך רשימה של מקטעים כשני מערכים: המקטע i נמשך מ-starts[i] עד ends[i]. הסר כמה שפחות מקטעים כך שאף שניים מהמקטעים שנותרו לא יחפפו. שני מקטעים שרק נוגעים זה בזה, כאשר אחד מסתיים בדיוק בנקודה שבה השני מתחיל, אינם חופפים.

כתוב פונקציה בשם eraseOverlapIntervals שמחזירה את המספר הקטן ביותר של מקטעים שעליך להסיר.

פונקציה

eraseOverlapIntervals(starts: integer-array, ends: integer-array) → integer

startsinteger-array: תחילתו של כל מקטע
endsinteger-array: סוף כל מקטע, באותו אינדקס כמו תחילתו
מחזירהinteger: המספר הקטן ביותר של קטעים שיש להסיר כדי שהקטעים הנותרים לא יחפפו

אילוצים

1 ≤ starts.length == ends.length ≤ 5000
-5 × 10⁴ ≤ starts[i] < ends[i] ≤ 5 × 10⁴
המרווחים אינם ממוינים. שני מרווחים עשויים להיות זהים.

דוגמאות

קלט: starts = [3, 1, 5, 2]ends = [6, 4, 7, 3]
פלט: 2
הסבר: בסדר ההתחלה, הטווחים הם [1,4], [2,3], [3,6] ו-[5,7]. השאר את [2,3] ואת [3,6], שרק נוגעים זה בזה, והסר את 2 האחרים. אי אפשר להשאיר שלושה: [1,4] חופף ל-[2,3], ו-[3,6] חופף ל-[5,7], ובכל שלושה מתוך הארבעה מופיע אחד מהזוגות האלה.

קלט: starts = [4, 1, 2]ends = [6, 2, 4]
פלט: 0
הסבר: [1,2], [2,4] ו-[4,6] נפגשים מקצה לקצה ואינם חופפים לעולם, לכן לא מסירים שום דבר והתשובה היא 0.

+17 בדיקות נסתרות בשליחה

שאלת המשך

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

פתרון

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

להשאיר או להסיר כל אחד מהמרווחים

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

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

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

בדוגמה הראשונה, המקטעים הממוינים הם [1,4], [2,3], [3,6], [5,7]. שמירת [1,4] חוסמת את [2,3] ואת [3,6], שמתחילים לפני 4, ומשאירה מקום ל-[5,7]: שני מקטעים נשמרו. הסרת [1,4] ושמירת [2,3] ואחריו [3,6] גם היא משאירה שני מקטעים. אף ענף לא מגיע ל-3, ולכן מסירים 4-2 = 2.

כל מקטע יכול להכפיל את מספר הענפים, ולכן n מקטעים מובילים לעד 2^n נתיבים. אפילו שלושים מקטעים שאינם חופפים כבר משמעותם יותר ממיליארד קריאות, והבדיקות מגיעות עד 5000 מקטעים. הרקורסיה גם מגיעה לעומק של n רמות: 5000 קריאות בבדיקות הגדולות ביותר, מעבר למגבלת ברירת המחדל של Python, שהיא 1,000.

אלגוריתם

מיינו את הקטעים לפי נקודת ההתחלה, תוך שמירה על הקשר בין כל נקודת התחלה לנקודת הסיום שלה.
הגדירו את mostKept(i, last): המספר המרבי של קטעים שאפשר להשאיר החל מהמיקום i, כאשר last הוא המיקום של הקטע האחרון שהשארנו (-1 אם אין כזה).
אם עברנו את סוף הרשימה, החזירו 0. אחרת, התחילו מ-mostKept(i+1, last), התוצאה של הסרת הקטע i.
אם הקטע i מתחיל בנקודת הסיום של הקטע last או אחריה, נסו גם את 1 + mostKept(i+1, i) והשאירו את התוצאה הגדולה יותר.
החזירו את n פחות mostKept(0, -1).

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)

    def most_kept(i, last):
        # The most intervals you can keep among i..n-1, when interval last
        # is the latest one kept so far (-1: nothing kept yet).
        if i == n:
            return 0
        best = most_kept(i + 1, last)  # remove interval i
        if last == -1 or intervals[i][0] >= intervals[last][1]:
            best = max(best, 1 + most_kept(i + 1, i))  # keep interval i
        return best

    return n - most_kept(0, -1)

השרשרת הארוכה ביותר באמצעות תכנות דינמי

נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר

האינטואיציה

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

המקטע שנשאר ממש לפני i חייב להסתיים בנקודת starts[i] או לפניה. כל מקטע כזה מופיע קודם בסדר הממויין: הוא מתחיל לפני שהוא מסתיים, ולכן הוא מתחיל לפני starts[i]. מכאן נובע ש-chain[i] = 1 + chain[j] עבור j הקודם הטוב ביותר שעבורו ends[j] ≤ starts[i], או 1 אם אין מקטע מתאים. הערך הגדול ביותר ב-chain הוא המספר המרבי שאפשר להשאיר.

בדוגמה הראשונה, לאחר מיון לפי [1,4], [2,3], [3,6], [5,7], הערכים הם 1, 1, 2 ו-2: [3,6] יכול לבוא אחרי [2,3], ו-[5,7] יכול לבוא אחרי [1,4] או [2,3]. השרשרת הארוכה ביותר היא באורך 2, ולכן מסירים 4-2 = 2.

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

אלגוריתם

מיינו את המקטעים לפי נקודת ההתחלה, תוך שמירה על ההתאמה בין כל נקודת התחלה לנקודת הסיום שלה.
הגדירו chain[i] = 1 עבור כל מקטע.
עבור כל i וכל j < i שעבורו ends[j] ≤ starts[i], הגדירו את chain[i] ל-chain[j]+1 כאשר הערך הזה גדול יותר.
החזירו את n פחות הערך הגדול ביותר ב-chain.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(starts, ends))  # by start time
    n = len(intervals)
    # chain[i]: the most intervals you can keep when interval i is the last one kept
    chain = [1] * n
    for i in range(n):
        for j in range(i):
            if intervals[j][1] <= intervals[i][0] and chain[j] + 1 > chain[i]:
                chain[i] = chain[j] + 1
    return n - max(chain)

חמדני: שמור את הקטע שמסתיים ראשון

האינטואיציה

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

אחרי שמשאירים אותו, כל מרווח שמתחיל לפני הסיום שלו חופף לו ויש להסירו. מה שנשאר הוא אותה השאלה לגבי המרווחים שמתחילים בסיום הזה או אחריו, ולכן יש להחיל שוב את אותו כלל. בפועל: ממיינים לפי סיום, עוברים על הרשימה וזוכרים את lastEnd, הסיום של המרווח האחרון שהשארנו. משאירים מרווח שמתחיל ב-lastEnd או אחריו; כל מרווח אחר נחשב למרווח שהוסר.

בדוגמה הראשונה, לאחר מיון לפי סיום, הסדר הוא [2,3], [1,4], [3,6], [5,7]. משאירים את [2,3], ולכן lastEnd = 3. [1,4] מתחיל ב-1, לפני 3: מסירים אותו. [3,6] מתחיל ב-3, לא לפני 3: משאירים אותו, lastEnd = 6. [5,7] מתחיל ב-5, לפני 6: מסירים אותו. הוסרו שני מרווחים.

מפתחות אחרים עשויים להיראות מפתים, אבל נכשלים. מיון לפי התחלה משאיר את [0,100] כשהוא מכסה את [1,2], [3,4] ואת [5,6], ומסיר שלושה מרווחים במקום אחד. השארת המרווח הקצר ביותר נכשלת עבור [1,5], [4,7], [6,10]: המרווח הקצר [4,7] חופף לשני האחרים, ולכן השארתו מחייבת הסרה של שני מרווחים, כשאפשר להסתפק באחד. הסיום הוא המפתח שמשאיר את מרב המקום לכל מה שבא אחריו.

המיון דורש O(n log n) והמעבר על הרשימה דורש O(n). העותק הממויין של המרווחים דורש O(n) מקום.

אלגוריתם

מיין את הקטעים לפי נקודת הסיום, תוך שמירה על כל נקודת סיום עם נקודת ההתחלה שלה.
השאר את הקטע הראשון: הגדר את lastEnd לנקודת הסיום שלו ואת removed ל־0.
עבור כל קטע עוקב, אם הוא מתחיל בנקודת lastEnd או אחריה, השאר אותו והגדר את lastEnd לנקודת הסיום שלו.
אחרת, הוסף 1 ל־removed.
החזר את removed.

def eraseOverlapIntervals(starts, ends):
    intervals = sorted(zip(ends, starts))  # by end time
    removed = 0
    last_end = intervals[0][0]  # the interval that ends first is always kept
    for end, start in intervals[1:]:
        if start >= last_end:
            last_end = end  # it fits after the last kept interval: keep it
        else:
            removed += 1  # it overlaps the last kept interval: remove it
    return removed

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

רוב התשובות השגויות נובעות ממפתח המיון או מההשוואה בנקודת מגע.

התייחסות למקטעים שנוגעים זה בזה כאל מקטעים חופפים. אם משתמשים ב־start > lastEnd במקום ב־start ≥ lastEnd, השרשרת [1,2], [2,4], [4,6] מאבדת את [2,4], שמתחיל בדיוק במקום שבו [1,2] מסתיים, והתשובה מתקבלת כ־1 במקום 0.
מיון לפי נקודת ההתחלה ותמיד השארת המקטע המוקדם יותר כשיש חפיפה. מקטע רחב [0,100] דוחק לאחר מכן את [1,2], [3,4] ואת [5,6]. אם ממיינים לפי נקודת ההתחלה, השאירו את המקטע מבין שני המקטעים החופפים שמסתיים ראשון.
השוואת כל מקטע לשכן שלו ברשימה הממוינת במקום למקטע האחרון שהשארתם. לאחר הסרת [1,4], יש לבדוק את המקטע הבא מול נקודת הסיום של [2,3], ולא מול 4.
מיון starts ו־ends כשתי רשימות נפרדות. כל נקודת סיום חייבת להישאר יחד עם נקודת ההתחלה שלה, אחרת משווים נקודת התחלה לנקודת סיום של מקטע אחר.
החזרת מספר המקטעים שהשארתם. השאלה מבקשת את מספר המקטעים שהוסרו, כלומר n פחות המספר הזה.

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

מהי סיבוכיות הזמן של מרווחים שאינם חופפים?

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

למה מיון לפי שעת הסיום מוביל להסרה של המספר הקטן ביותר של מקטעים?

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

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

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

האם בעיית הקטעים שאינם חופפים זהה לבעיית בחירת הפעילויות?

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

Python

def eraseOverlapIntervals(starts, ends):
    # כתבו כאן קוד

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

starts = [3, 1, 5, 2]
ends = [6, 4, 7, 3]

צפוי

Non-overlapping Intervals

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

להשאיר או להסיר כל אחד מהמרווחים

השרשרת הארוכה ביותר באמצעות תכנות דינמי

חמדני: שמור את הקטע שמסתיים ראשון

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

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

בעיות דומות