Merge Intervals
Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Sample Input: [[1,3],[2,6],[8,10],[15,18]]
Expected Output: [[1,6],[8,10],[15,18]]
The interval [1,3] overlaps with [2,6], so they are merged into [1,6].
Constraints
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
How We Solve This
- First, sort all intervals by their start time.
- Start with the first interval as the current one.
- Go through the rest one by one:
- If the next interval overlaps, merge it into the current interval.
- If it doesn’t overlap, save the current interval and move to the next one.
- At the end, the saved intervals are the final merged answer.
Edge Cases to Consider
Empty Input
Input:
[]Output:
[]The algorithm should return an empty list for empty input.
Single Interval
Input:
[[5, 8]]Output:
[[5, 8]]If there's only one interval, it's returned as is.
All Overlap
Input:
[[1, 5], [2, 4], [3, 6]]Output:
[[1, 6]]All intervals merge into a single, all-encompassing interval.
No Overlap
Input:
[[1, 2], [4, 5], [8, 9]]Output:
[[1, 2], [4, 5], [8, 9]]When no intervals overlap, the list is returned unchanged.