Insert Interval

Q: מהי סיבוכיות הזמן של Insert Interval?

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

Q: במה Insert Interval שונה מ-Merge Intervals?

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

Q: איך בודקים אם שני טווחים חופפים?

למקטעים [a, b] ו־ [c, d] יש לפחות נקודה משותפת בדיוק כאשר a ≤ d ו־ c ≤ b . כך גם מקטעים שנוגעים זה בזה, כגון [2, 4] ו־ [4, 8] , נחשבים לחופפים, וזה מה שהבעיה הזאת דורשת. אם מקטעים שנוגעים זה בזה היו צריכים להישאר נפרדים, היית משתמש במקום זאת ב־ a < d ו־ c < b .

Q: האם חיפוש בינארי יכול להפוך את Insert Interval למהיר יותר?

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

בינוניקטעים

+10

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

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

פונקציה

insertInterval(starts: integer-array, ends: integer-array, newStart: integer, newEnd: integer) → integer-2d-array

startsinteger-array: תחילת כל מרווח, בסדר עולה
endsinteger-array: סוף כל מקטע, התאמה של נקודות ההתחלה
newStartinteger: תחילת המרווח שיש להוסיף
newEndinteger: סוף המרווח שיש להוסיף
מחזירהinteger-2d-array: הקטעים שאחרי ההוספה כזוגות [start, end], ממוינים לפי start

אילוצים

1 ≤ starts.length == ends.length ≤ 2000
0 ≤ starts[i] ≤ ends[i] ≤ 10⁵
ends[i] < starts[i+1]: הטווחים ממוינים לפי נקודת ההתחלה, ואף שניים מהם אינם חופפים או נוגעים זה בזה.
0 ≤ newStart ≤ newEnd ≤ 10⁵

דוגמאות

קלט: starts = [1, 5, 10, 15]ends = [3, 7, 12, 18]newStart = 6newEnd = 11
פלט: [[1, 3], [5, 12], [15, 18]]
הסבר: [6, 11] חופף ל־[5, 7] ול־[10, 12], ולכן שלושת הטווחים מתאחדים ל־[5, 12]. [1, 3] מסתיים לפני 6 ו־[15, 18] מתחיל אחרי 12, ולכן שניהם נשארים כפי שהם.

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

קלט: starts = [1, 9]ends = [2, 10]newStart = 5newEnd = 6
פלט: [[1, 2], [5, 6], [9, 10]]
הסבר: [5, 6] נמצאים ברווח שבין 2 ל־9 ולא נוגעים באף אחד מהשכנים, לכן הם נכנסים ביניהם ושום דבר לא מתמזג.

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

שאלת המשך

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

רמזים

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

נפתחו 0 מתוך 3

פתרון

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

הוסף אותו ומזג את הכול שוב

האינטואיציה

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

הרץ זאת על הדוגמה הראשונה. הרשימה הופכת ל־[1, 3], [5, 7], [6, 11], [10, 12], [15, 18]. [1, 3] נשאר לבדו, כי 5 גדול מ־3. 6 קטן מ־7 או שווה לו, לכן [5, 7] מתרחב ל־[5, 11]. 10 קטן מ־11 או שווה לו, לכן הוא מתרחב ל־[5, 12]. 15 גדול מ־12, לכן [15, 18] מתחיל מקטע חדש.

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

אלגוריתם

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

def insertInterval(starts, ends, newStart, newEnd):
    intervals = list(zip(starts, ends))
    intervals.append((newStart, newEnd))
    intervals.sort()
    merged = []
    for start, end in intervals:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)  # overlaps or touches: stretch
        else:
            merged.append([start, end])  # a real gap: a new interval begins
    return merged

מעבר אחד בשלושה חלקים

האינטואיציה

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

שנית, כל מקטע שבו starts[i] ≤ mergedEnd חופף למקטע שאת בונה או נוגע בו. שלבי אותו: mergedStart נעשה לתחילת המקטע הקטנה יותר, ו-mergedEnd לסוף המקטע הגדול יותר. המקטעים ברצף הזה סמוכים זה לזה, כי הרשימה ממוינת. ברגע שמקטע מתחיל אחרי mergedEnd, כל מקטע שבא אחריו מתחיל עוד יותר ימינה, ולכן שום דבר אחריו לא יכול להתמזג. הוסיפי את המקטע הממוזג; שלב זה מכסה גם את המקרה שבו הרצף ריק והמקטע החדש מתווסף לבדו.

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

עקבי אחר הדוגמה הראשונה. [1, 3] מסתיים לפני 6: העתיקי אותו. [5, 7] מתחיל ב-5, שהוא לכל היותר 11: המקטע הממוזג נעשה ל-[5, 11]. [10, 12] מתחיל ב-10, לכל היותר 11: הוא נעשה ל-[5, 12]. [15, 18] מתחיל אחרי 12, לכן הוסיפי את [5, 12] והעתיקי את [15, 18]. עוברים על כל מקטע פעם אחת, ולכן זמן הריצה הוא O(n), והזיכרון הנוסף היחיד הוא התוצאה עצמה.

אלגוריתם

העתק את הטווחים לתוצאה כל עוד ends[i] < newStart.
הגדר את mergedStart = newStart ואת mergedEnd = newEnd.
כל עוד starts[i] ≤ mergedEnd, הגדר את mergedStart להתחלה הקטנה יותר ואת mergedEnd לסוף הגדול יותר, והמשך הלאה.
הוסף את [mergedStart, mergedEnd].
העתק את הטווחים הנותרים והחזר את התוצאה.

def insertInterval(starts, ends, newStart, newEnd):
    n = len(starts)
    result = []
    i = 0
    # 1. Intervals that end before the new one starts stay as they are.
    while i < n and ends[i] < newStart:
        result.append([starts[i], ends[i]])
        i += 1
    # 2. Intervals that overlap or touch the new one fold into it.
    mergedStart, mergedEnd = newStart, newEnd
    while i < n and starts[i] <= mergedEnd:
        mergedStart = min(mergedStart, starts[i])
        mergedEnd = max(mergedEnd, ends[i])
        i += 1
    result.append([mergedStart, mergedEnd])
    # 3. Intervals that start after the merged one ends stay as they are.
    while i < n:
        result.append([starts[i], ends[i]])
        i += 1
    return result

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

הלולאה קצרה, ולכן רוב הבאגים נובעים מהשוואה שגויה אחת או ממקרה שנשכח בקצוות הרשימה.

שימוש באי־שוויון שגוי עבור מרווחים שנוגעים זה בזה. עם ends[i] ≤ newStart בלולאה הראשונה, או starts[i] < mergedEnd בשנייה, [2, 4] ו־[4, 8] נשארים נפרדים. מרווחים שנוגעים זה בזה מתמזגים, לכן התנאי הראשון חייב להיות מחמיר והשני לא.
מיזוג מרווחים שרק נראים סמוכים. [1, 2] ו־[3, 4] אינם חולקים אף נקודה, ולכן השוואה מול mergedEnd + 1 מחברת מרווחים שאמורים להישאר נפרדים.
השארת newStart כתחילת המרווח הממוזג. כאשר המרווח החדש מתחיל בתוך מרווח ישן, כפי ש־[6, 11] עושה בתוך [5, 7], התוצאה מתחילה ב־5. בחרו את הקטן מבין שני ערכי ההתחלה.
הוספת המרווח החדש רק כאשר הוא חופף למשהו. כשהוא מופיע לפני כל המרווחים, אחרי כולם או ברווח ביניהם, הלולאה האמצעית אינה פועלת, ועדיין צריך להוסיף את המרווח החדש.
קריאת starts[i] או ends[i] לפני בדיקת i < n. כשהמרווח החדש מגיע מעבר למרווח האחרון, האינדקס חורג מסוף המערכים.

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

מהי סיבוכיות הזמן של Insert Interval?

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

במה Insert Interval שונה מ-Merge Intervals?

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

איך בודקים אם שני טווחים חופפים?

למקטעים [a, b] ו־[c, d] יש לפחות נקודה משותפת בדיוק כאשר a ≤ d ו־c ≤ b. כך גם מקטעים שנוגעים זה בזה, כגון [2, 4] ו־[4, 8], נחשבים לחופפים, וזה מה שהבעיה הזאת דורשת. אם מקטעים שנוגעים זה בזה היו צריכים להישאר נפרדים, היית משתמש במקום זאת ב־a < d ו־c < b.

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

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

Python

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

מקרי בדיקה

מקרה 1

מקרה 2

מקרה 3

קלט

starts = [1, 5, 10, 15]
ends = [3, 7, 12, 18]
newStart = 6
newEnd = 11

צפוי

[[1, 3], [5, 12], [15, 18]]