Merge Intervals
ניתנת לך קבוצה של מקטעים, שכל אחד מהם הוא טווח של מספרים שלמים מנקודת התחלה ועד נקודת סיום. מזג כל קבוצה של מקטעים חופפים למקטע אחד שמכסה את כל הקבוצה, והחזר את המקטעים הממוזגים כשהם ממוינים לפי נקודת ההתחלה. מקטעים שרק נוגעים זה בזה, כמו [1, 4] ו-[4, 5], נחשבים לחופפים.
המקטעים ניתנים כשני מערכים באורך זהה: מקטע i הוא [starts[i], ends[i]]. עליך להחזיר מערך דו־ממדי, רשימה של זוגות [start, end].
פונקציה
- startsinteger-array
- תחילת כל מרווח
- endsinteger-array
- בסוף כל מרווח, באותו אינדקס כמו נקודת ההתחלה שלו
- מחזירהinteger-2d-array
- המרווחים שאוחדו כזוגות [start, end], ממוינים לפי start
אילוצים
1 ≤ starts.length == ends.length ≤ 1040 ≤ starts[i] ≤ ends[i] ≤ 104- המרווחים מגיעים בכל סדר שהוא.
- טווחים שנוגעים זה בזה רק בקצה נחשבים לחופפים.
דוגמאות
- קלט
- starts = [5, 1, 12, 3]ends = [7, 4, 14, 6]
- פלט
- [[1, 7], [12, 14]]
- הסבר
- לפי סדר ההתחלה, [1, 4] חופף ל־[3, 6], שחופף ל־[5, 7], ולכן שלושת הטווחים מתאחדים ל־[1, 7]. [12, 14] מתחיל אחרי 7 ונשאר בפני עצמו.
- קלט
- starts = [6, 1]ends = [9, 6]
- פלט
- [[1, 9]]
- הסבר
- הקטעים הם [6, 9] ו-[1, 6]. יש להם נקודה משותפת, 6, ומכיוון שנקודות מגע נחשבות לחפיפה, הם מתמזגים ל-[1, 9].
שאלת המשך
המרווחים מגיעים כשהם כבר מאוחדים וממוינים לפי נקודת ההתחלה, ועליך להוסיף מרווח חדש אחד. האם תוכל להחזיר את הרשימה המאוחדת בזמן O(n), בלי למיין שוב?
רמזים
פתחו אותם אחד אחד. כל רמז חושף קצת יותר.
התאם תחילה כל התחלה לסוף שלה, כדי שתעבוד עם מרווחים שלמים במקום עם שני מערכים נפרדים.
מיין את הטווחים לפי נקודת ההתחלה. לאחר מכן, טווח יכול לחפוף רק לקבוצה שמיד לפניו, ולעולם לא לקבוצה שנמצאת רחוק יותר לאחור.
עבור על הטווחים הממוינים תוך שמירה של הטווח האחרון שאוחד. אם נקודת ההתחלה הבאה קטנה או שווה לנקודת הסיום שלו, קבע את נקודת הסיום שלו לגדולה מבין שתי נקודות הסיום. אחרת, הקבוצה הזאת מסתיימת והטווח הבא פותח קבוצה חדשה.
פתרון
מיזוג זוגות בכל סדר מצריך מעברים חוזרים, כי כל מיזוג מרחיב טווח ומאפשר לו להגיע לטווחים שכבר בדקת. במקום זאת, מיין לפי נקודת ההתחלה. כך טווח יכול לחפוף רק לקבוצה שאתה בונה, ומעבר אחד מספיק כדי לסיים את העבודה.
מזג זוגות חופפים עד ששום דבר לא משתנה
נכונה, אבל לא מסתיימת בבדיקות הגדולות ביותר
האינטואיציה
הקטעים [a, b] ו-[c, d] חופפים כאשר c ≤ b ו-a ≤ d, ו-[min(a, c), max(b, d)] מכסה את שניהם. כל איחוד מסיר קטע אחד, ולכן התהליך נעצר, וברגע שמעבר מלא לא מוצא חפיפה, אין שני קטעים שנותרו שחולקים נקודה. מעבר אחד אינו מספיק: קטע מאוחד רחב יותר, וכעת הוא יכול להגיע לקטע שחלק קטן יותר שלו הושווה אליו מוקדם יותר במעבר.
מעבר משווה בערך n²/2 זוגות, וייתכן שיהיה צורך בעד n מעברים: O(n³). מעבר אחד על 10^4 קטעים כרוך כבר ב-5 × 10^7 השוואות.
אלגוריתם
- העתיקו את
startsואתends, ושמרו מונהnשל המרווחים הפעילים. - השוו כל מרווח
iלכל מרווח מאוחר יותרj. אם הם חופפים, הרחיבו אתiכך שיכסה אתj, העבירו את המרווח הפעיל האחרון למקוםjוהקטינו אתnבאחד. - אחרי איחוד, בדקו שוב את המקום
j, כי עכשיו נמצא בו מרווח אחר. - חזרו על המעברים עד שמעבר אחד לא מבצע איחוד.
- צרו זוג מכל נקודת התחלה פעילה ומהנקודה הסופית שלה, מיינו את הזוגות לפי נקודת ההתחלה והחזירו אותם.
def mergeIntervals(starts, ends):
s = list(starts)
e = list(ends)
n = len(s)
changed = True
while changed:
changed = False
i = 0
while i < n:
j = i + 1
while j < n:
if s[j] <= e[i] and s[i] <= e[j]:
# Intervals i and j overlap: interval i absorbs interval j.
s[i] = min(s[i], s[j])
e[i] = max(e[i], e[j])
# Move the last interval into slot j and drop the last slot.
n -= 1
s[j] = s[n]
e[j] = e[n]
changed = True
else:
j += 1
i += 1
return sorted([s[k], e[k]] for k in range(n))מיון לפי נקודת ההתחלה ומעבר אחד
האינטואיציה
לאחר המיון לפי נקודת ההתחלה, נקודת ההתחלה של המקטע הבא אינה מוקדמת יותר מאף נקודה בקבוצה האחרונה, שמסתיימת ב־e. אם נקודת ההתחלה שלו היא לכל היותר e, הוא חופף לקבוצה או נוגע בה, ומצטרף אליה, ו־e הופך לגדול מבין שתי נקודות הסיום. אם נקודת ההתחלה שלו אחרי e, גם שום מקטע מאוחר יותר לא יוכל להגיע בחזרה אל תוך הקבוצה, כי נקודות ההתחלה של המקטעים המאוחרים יותר נמצאות ימינה יותר. הקבוצה מסתיימת, והמקטע מתחיל קבוצה חדשה.
המיון עולה O(n log n), והסריקה עוברת על כל מקטע פעם אחת. הקבוצות נסגרות משמאל לימין, ולכן התוצאה מתקבלת כשהיא ממוינת לפי נקודת ההתחלה.
אלגוריתם
- התאימו כל התחלה לסוף שלה: המקטע
iהוא[starts[i], ends[i]]. - מיינו את הזוגות לפי נקודת ההתחלה.
- עברו על הזוגות הממוינים. אם התוצאה ריקה, או שהזוג מתחיל אחרי סוף המקטע המאוחד האחרון, הוסיפו את הזוג כמקטע חדש.
- אחרת, הגדירו את סוף המקטע המאוחד האחרון כגדול מבין הסוף שלו לסוף הזוג.
- החזירו את הרשימה המאוחדת.
def mergeIntervals(starts, ends):
intervals = sorted(zip(starts, ends))
merged = []
for start, end in intervals:
if merged and start <= merged[-1][1]:
if end > merged[-1][1]:
merged[-1][1] = end
else:
merged.append([start, end])
return merged
מלכודות ומקרי קצה
- השוואה באמצעות
<במקום≤. יש למזג גם טווחים שנוגעים זה בזה, כגון[1, 4]ו־[4, 5]. - הגדרת הסוף לסוף של הטווח החדש במקום לגדול מבין השניים.
[1, 10]ואחריו[2, 3]חייב להישאר[1, 10]. - מיון
startsבפני עצמו ואז קריאתendsבמיקומים החדשים, כך שהתחלה מקבלת את הסוף של טווח אחר. יש לצמד אותם קודם, או למיין את האינדקסים. - השוואה עם טווח הקלט הקודם במקום עם הטווח האחרון שמוזג. ב־
[1, 10],[2, 3],[4, 5], הטווח השלישי נמצא בתוך[1, 10], אף שהוא אינו נוגע ב־[2, 3]. - ב־C, אי־הגדרת
*returnSizeלמספר הטווחים שמוזגו ואת הגודל של כל עמודה ל־2.
שאלות נפוצות3
מהי סיבוכיות הזמן של Merge Intervals?
פתרון המיון והסריקה פועל בזמן O(n log n) עבור n קטעים: המיון עולה O(n log n) והסריקה O(n). הוא משתמש במקום נוסף של O(n) עבור הזוגות הממוינים והתוצאה.
למה למיין את הקטעים לפי נקודת ההתחלה ולא לפי נקודת הסיום?
כאשר ממיינים לפי נקודת ההתחלה, מרווח יכול לחפוף רק לקבוצה שבונים, ולכן השוואה אחת עם נקודת הסיום של אותה קבוצה מכריעה הכול. כאשר ממיינים לפי נקודת הסיום, מרווח מאוחר יותר יכול להתחיל לפני קבוצות שכבר סיימתם: [5, 6] מופיע לפני [1, 10], וסריקה קדימה תשאיר בטעות את 5 כנקודת ההתחלה.
האם אפשר למזג מקטעים בלי להשתמש בשטח נוסף?
כן, אם מותר לך לשנות את הקלט. מיין את הקטעים במקום, ואז כתוב כל קטע ממוזג בתחילת אותו מערך ושמור את האינדקס של הקטע האחרון שנכתב. זמן הריצה נשאר O(n log n), והזיכרון הנוסף היחיד הוא זה שהמיון של השפה שלך משתמש בו.
בעיות דומות
בעיות שמשתמשות באותם רעיונות. פתרון של שתיים או שלוש מהן מקבע את הדפוס.
def mergeIntervals(starts, ends):
# כתבו כאן את הקודבדיקה #1
בדיקה #2
ארגומנטים
starts = [5, 1, 12, 3] ends = [7, 4, 14, 6]
הפלט הצפוי
[[1, 7], [12, 14]]