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]]Explanation:
After sorting by start time: [[1,2],[2,3],[4,6],[6,9],[7,8]]. Intervals [1,2] and [2,3] overlap (touching at 2) and merge to [1,3]. Intervals [4,6], [6,9], and [7,8] all overlap: [4,6] and [6,9] touch at 6, and [7,8] is contained within [4,9], so all three merge into [4,9].
Constraints
- •
1 ≤ intervals.length ≤ 10⁴ - •
intervals[i].length == 2 - •
0 ≤ starti ≤ endi ≤ 10⁴