Merge Intervals
Combine overlapping intervals into disjoint ones. Sort by start, then greedily extend the current interval whenever the next overlaps it.
- Category
- Greedy
- Time complexity
- O(n log n)
- Space complexity
- O(n)
Pseudocode
sort intervals by start if next overlaps last result extend last result else append next as new
Reference implementation
iv.sort()
for s, e in iv:
if out and s <= out[-1][1]:
out[-1][1] = max(out[-1][1], e)
else: out.append([s, e])