Description
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
Examples
Input:
intervals = [[1,3],[2,6],[8,10],[15,18]]Output:
[[1,6],[8,10],[15,18]]Explanation:
Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
Input:
intervals = [[1,4],[4,5]]Output:
[[1,5]]Explanation:
Intervals [1,4] and [4,5] are considered overlapping.
Input:
intervals = [[2,3],[4,6],[1,2],[7,8],[6,9]]Output:
[[1,3],[4,9],[7,8]]Explanation:
After sorting by start time: [[1,2],[2,3],[4,6],[6,9],[7,8]]. Intervals [1,2] and [2,3] overlap and merge to [1,3]. Intervals [4,6] and [6,9] overlap (touching at 6) and merge to [4,9]. However, [7,8] is completely contained within [4,9], so the final result merges all three into [4,9]. Final output: [[1,3],[4,9]].
Constraints
- •
1 ≤ intervals.length ≤ 10⁴ - •
intervals[i].length == 2 - •
0 ≤ starti ≤ endi ≤ 10⁴