Merge Intervals

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

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

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

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

מזגו כל קבוצה של מקטעים חופפים. גם מקטעים שרק נוגעים זה בזה בקצה נחשבים חופפים. החזירו את המקטעים המאוחדים כמערך דו־ממדי [[start, end], ...], ממוינים לפי נקודת ההתחלה.

לדוגמה, starts = [5, 1, 12, 3] ו-ends = [7, 4, 14, 6] מתארים את [5, 7], [1, 4], [12, 14] ואת [3, 6], שמתאחדים ל-[[1, 7], [12, 14]].

אילוצים: 1 <= starts.length == ends.length <= 10^4, 0 <= starts[i] <= ends[i] <= 10^4.