56. Merge Intervals
You are handed a list intervals where each entry [start, end] marks a closed range on the number line. Some ranges collide with each other; wherever two ranges touch or overlap, they really describe one continuous stretch.
Write a function that receives intervals (a list of [start, end] pairs, in no particular order) and returns the smallest possible list of non-overlapping intervals covering exactly the same points, sorted by start in increasing order.
Two intervals that merely touch, like [1, 4] and [4, 5], count as overlapping and must be fused into [1, 5].
Example 1:
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Output: [[1, 6], [8, 10], [15, 18]]
Explanation: [1, 3] and [2, 6] overlap (they share the stretch from 2 to 3), so they fuse into [1, 6]. The other two intervals stay untouched.
Example 2:
Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: The two ranges meet at the point 4, so together they cover one unbroken stretch [1, 5].
Constraints:
- 1 ≤ n ≤ 10⁴
- 0 ≤ start ≤ end ≤ 10⁹
Hints:
If the intervals were sorted by start, where could an interval's overlapping partners possibly sit?
After sorting by start, walk left to right keeping one 'current' merged interval. Each next interval either extends it (its start is <= the current end) or begins a fresh one.
Extending means taking the max of the two ends — a later interval can be completely swallowed by the current one.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
Expected output: [[1, 6], [8, 10], [15, 18]]