Insert Interval
מקבלים מרווחים ממוינים לפי נקודת ההתחלה בשני מערכים: מרווח i הוא [starts[i], ends[i]], ואף שני מרווחים אינם חופפים או נוגעים זה בזה. הוסיפו את המרווח החדש [newStart, newEnd], מזגו אותו עם כל מרווח שהוא חופף או נוגע בו, והחזירו את כל המרווחים כזוגות [start, end] ממוינים לפי נקודת ההתחלה.
מרווחים נוגעים זה בזה כאשר אחד מסתיים במקום שבו השני מתחיל, כמו [2, 4] ו-[4, 8], ומרווחים שנוגעים זה בזה מתמזגים. ל-[1, 2] ול-[3, 4] אין נקודה משותפת, ולכן הם נשארים נפרדים.
פונקציה
- startsinteger-array
- תחילת כל אחד מהטווחים, בסדר עולה
- endsinteger-array
- סוף כל מקטע, התחלות תואמות
- newStartinteger
- תחילת המרווח להוספה
- newEndinteger
- סוף הטווח שיש להוסיף
- מחזירהinteger-2d-array
- את המרווחים שאחרי ההוספה כזוגות [start, end], ממוינים לפי start
אילוצים
1 ≤ starts.length == ends.length ≤ 20000 ≤ starts[i] ≤ ends[i] ≤ 105ends[i] < starts[i+1]: המרווחים ממוינים לפי נקודת ההתחלה, ואף שניים מהם אינם חופפים או נוגעים זה בזה.0 ≤ newStart ≤ newEnd ≤ 105
דוגמאות
- קלט
- 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 ואינו נוגע באף אחד מהשכנים, ולכן הוא נכנס ביניהם ושום דבר לא מתמזג.
שאלת המשך
אם תכניס מרווחים רבים בזה אחר זה, איך תאחסן אותם כך שכל הוספה תעלה O(log n) בתוספת צעד אחד לכל מרווח ישן שהיא בולעת?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
המרווחים הישנים ממוינים וכבר אינם חופפים זה לזה. אילו מהם המרווח החדש יכול לשנות, והיכן הם יכולים להימצא ברשימה?
המרווחים מתחלקים לשלושה רצפים: אלה שמסתיימים לפני
newStart, אלה שחופפים ל־[newStart, newEnd]או נוגעים בו, ואלה שמתחילים אחרי שהמרווח הממוזג מסתיים. הרצף האמצעי הוא בלוק רציף אחד.עוברים על הרשימה פעם אחת. מעתיקים את הטווחים כל עוד הם מסתיימים לפני
newStart. לאחר מכן, כל עוד הטווח הבא מתחיל בנקודת הסיום שאת בונה או לפניה, מרחיבים את הטווח החדש כך שיכלול אותו. מוסיפים את הטווח החדש, ואז מעתיקים את כל מה שנותר.
פתרון
המרווחים הישנים ממוינים ונפרדים זה מזה, ולכן רק המרווח החדש יכול לגרום למיזוג. כך הרשימה מתחלקת לשלושה רצפים: מרווחים שמסתיימים לפני שהוא מתחיל, מרווחים שחופפים לו או נוגעים בו, ומרווחים שמתחילים אחרי שהוא מסתיים. מעתיקים את הרצף הראשון, מאחדים את הרצף האמצעי למרווח אחד ומעתיקים את האחרון. מעבר אחד, ללא מיון.
הוסף אותו ומזג הכול שוב
האינטואיציה
שימוש חוזר במיזוג מקטעים: מוסיפים את המקטע החדש, ממיינים את כל n+1 המקטעים לפי נקודת ההתחלה, ועוברים עליהם תוך שמירה של המקטע הממוזג האחרון. אחרי המיון, מקטע יכול לחפוף רק לקבוצה שמיד לפניו, ולכן כשההתחלה הבאה נמצאת בנקודת הסיום השמורה או לפניה, מאריכים את נקודת הסיום; אחרת נוצר פער ומתחיל מקטע חדש.
המיון עולה 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מעבר אחד בשלושה חלקים
האינטואיציה
הרשימה ממוינת והמרווחים שבה אינם חופפים, לכן המרווחים שנפגשים עם החדש יוצרים רצף רציף אחד. לכל מה שלפני הרצף מתקיים ends[i] < newStart: הוא מסתיים לפני שהמרווח החדש מתחיל. התנאי מחמיר, כי מרווח שמסתיים בדיוק ב-newStart נוגע במרווח החדש ויש למזג ביניהם.
בתוך הרצף, מרווח שעבורו starts[i] ≤ mergedEnd חופף למרווח שאת בונה או נוגע בו, ולכן הוא מרחיב אותו להתחלה המוקדמת מבין השתיים ולקצה המאוחר מבין השניים. המרווח הראשון שמתחיל אחרי mergedEnd מסיים את הרצף, כי כל מרווח שבא אחריו מתחיל ימינה יותר. כשהרצף ריק, המרווח החדש נכנס לבדו. בדוגמה הראשונה, [1, 3] מועתק, [5, 7] ו-[10, 12] מרחיבים את [6, 11] ל-[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]נשארים נפרדים. הבדיקה הראשונה מחמירה, והשנייה אינה מחמירה. - השוואה מול
mergedEnd + 1. כך מחברים את[1, 2]ואת[3, 4], שאינם חולקים אף נקודה. - השארת
newStartכתחילת המקטע המאוחד.[6, 11]מתחיל בתוך[5, 7], ולכן התוצאה מתחילה ב-5. - הוספת המקטע החדש רק כשהוא חופף למשהו. כשהוא נמצא בפער או מעבר לאחד הקצוות, כמו
[5, 6], הלולאה האמצעית לא רצה כלל, ועדיין צריך להוסיף אותו. - קריאת
starts[i]לפני בדיקתi < n. אם המקטע החדש מגיע מעבר למקטע האחרון, האינדקס חורג מהסוף.
שאלות נפוצות3
מהי סיבוכיות הזמן של Insert Interval?
הפתרון במעבר אחד פועל בזמן O(n), מכיוון שכל טווח מועתק או מאוחד פעם אחת, ומשתמש במקום O(n) עבור תוצאה של עד n+1 טווחים. הוספת הטווח ומיון מחדש אורכים O(n log n).
במה Insert Interval שונה מ-Merge Intervals?
מיזוג טווחים מתחיל מרשימה לא ממוינת שבה כל טווח יכול לחפוף לכל טווח אחר, ולכן קודם כול ממיינים אותה. כאן הרשימה ממוינת והטווחים הישנים אינם נוגעים זה בזה לעולם, ולכן רק הטווח החדש יכול לגרום למיזוג, והטווחים שהוא מתמזג איתם יוצרים רצף אחד. מעבר יחיד מספיק.
איך בודקים אם שני טווחים חופפים?
[a, b] ו-[c, d] חולקים נקודה בדיוק כאשר a ≤ d וגם c ≤ b. כך גם מרווחים שנוגעים זה בזה, כגון [2, 4] ו-[4, 8], נחשבים לחופפים, כפי שהבעיה דורשת. כדי להפריד בין מרווחים שנוגעים זה בזה, השתמשו ב-a < d וב-c < b.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
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]]