Description
Merge all overlapping closed intervals and return the resulting disjoint intervals in ascending order.
Solution
def merge(intervals):
result = []
for start,end in sorted(intervals):
if result and start <= result[-1][1]:
result[-1][1] = max(result[-1][1],end)
else:
result.append([start,end])
return resultExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[[5,8],[1,3],[2,6]]]- Output
[[1,8]]
The middle overlap joins all three intervals.
Example 2
- Input
[[[1,2],[2,3]]]- Output
[[1,3]]
Closed intervals touching at 2 merge.
Example 3
- Input
[[[4,4]]]- Output
[[4,4]]
A single interval stays unchanged.
Approach
Sort by start and extend the last output interval whenever an overlap occurs.
Time & space
O(n log n) time; O(n) space including sorting and output. Here n is the input length.