Merge Intervals
MediumIntervals · Meta
You are given an array intervals, where intervals[i] = [start, end] is a closed interval (both endpoints included). The intervals are not in any particular order.
Merge every group of overlapping intervals into a single interval, and return the merged intervals sorted by start.
Two intervals overlap if they share at least one point, so intervals that only touch at an endpoint (such as [1, 4] and [4, 6]) are merged too. The result must cover exactly the same points as the input, with no two result intervals overlapping.
Example 1
- Input:
- intervals = [[6, 8], [1, 3], [2, 4], [9, 12]]
- Output:
- [[1, 4], [6, 8], [9, 12]]
- Explanation
- Sorted by start the list is
[1, 3], [2, 4], [6, 8], [9, 12].[1, 3]and[2, 4]overlap and become[1, 4]. The others do not touch anything, so they stay separate.
Example 2
- Input:
- intervals = [[1, 10], [2, 3], [4, 5]]
- Output:
- [[1, 10]]
- Explanation
- Both short intervals lie completely inside
[1, 10], so everything merges into[1, 10].
Example 3
- Input:
- intervals = [[1, 4], [4, 6]]
- Output:
- [[1, 6]]
- Explanation
- The intervals share the point 4. Endpoints are inclusive, so they overlap and merge into
[1, 6].
Constraints
1 <= intervals.length <= 10^4intervals[i].length == 20 <= start <= end <= 10^4