Non-overlapping Intervals

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

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

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

+10

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

פונקציה

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 = [0, 0, 0]ends = [5, 5, 5]
פלט: 2
הסבר: כל שלושת הטווחים הם [0,5], ולכן כל שניים מהם חופפים. אחד נשאר, ומסירים את 2.

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

שאלת המשך

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

פתרון

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

השארה או הסרה של כל מרווח

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

האינטואיציה

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

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

אלגוריתם

מיינו את הקטעים לפי נקודת ההתחלה, תוך שמירה על הקשר בין כל נקודת התחלה לנקודת הסיום שלה.
הגדירו את 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] או לפניו, ולכן הוא מתחיל מוקדם יותר ומופיע קודם בסדר הממויין. מכאן מתקבל chain[i] = 1 + chain[j] עבור ה-j המתאים ביותר, או 1 אם אף אחד מהם אינו מתאים. בדוגמה הראשונה הערכים הם 1, 1, 2 ו-2, לכן משאירים 2 ומסירים 2.

הלולאה הכפולה מבצעת n(n-1)/2 בדיקות: בערך 12.5 מיליון כאשר n = 5000.

אלגוריתם

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

גרידי: שמור את הטווח שמסתיים ראשון

האינטואיציה

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

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

המיון עולה O(n log 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] נותנת 1 במקום 0.
מיון לפי נקודת ההתחלה והשארת המקטע המוקדם יותר במקרה של חפיפה. מקטע רחב [0,100] דוחק אחריו את [1,2], [3,4] ו-[5,6]: שלוש הסרות במקום אחת.
השוואת כל מקטע לשכנו ברשימה הממוינת במקום למקטע האחרון שהושאר. בדוגמה הראשונה, יש לבדוק את [3,6] מול נקודת הסיום של [2,3], ולא של [1,4] שהוסר, אחרת התוצאה תהיה 3.
מיון starts ו-ends כשתי רשימות נפרדות. כל נקודת סיום חייבת להישאר עם נקודת ההתחלה שלה.
החזרת מספר המקטעים שהשארת במקום מספר המקטעים שהסרת.

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

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

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

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

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

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

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

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

בדיקה #1

בדיקה #2

בדיקה #3

ארגומנטים

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

הפלט הצפוי

Non-overlapping Intervals

פונקציה

אילוצים

דוגמאות

רמזים

פתרון

השארה או הסרה של כל מרווח

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

גרידי: שמור את הטווח שמסתיים ראשון

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

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

בעיות דומות