Given an array of intervals where intervals[i] = [start, end], merge every group of overlapping intervals and return the non-overlapping result, sorted by start.
Intervals that touch at an endpoint, like [1, 4] and [4, 5], count as overlapping.
Examples
Example 1
- Input
- intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
- Output
- [[1, 6], [8, 10], [15, 18]]
- Why
- [1, 3] and [2, 6] overlap, so they merge into [1, 6].
Example 2
- Input
- intervals = [[1, 4], [4, 5]]
- Output
- [[1, 5]]
Example 3
- Input
- intervals = [[4, 7], [1, 4]]
- Output
- [[1, 7]]
Constraints
1 <= intervals.length <= 10^40 <= start <= end <= 10^4