35. Merge Intervals
Combine intervals that overlap so the result describes exactly the same covered points without overlapping output intervals. Sort the resulting intervals by their positions on the line.
These intervals are closed, so sharing an endpoint counts as overlap. Do not apply the different endpoint rule used by the scheduling problems.
Example 1
Input
[[1,3],[2,6],[8,10],[15,18]]
Output
[[1,6],[8,10],[15,18]]
Explanation: Only the first two overlap.
Example 2
Input
[[1,4],[2,3]]
Output
[[1,4]]
Explanation: A contained interval must not shorten the current end.
Example 3
Input
[[1,2],[2,3]]
Output
[[1,3]]
Explanation: A shared endpoint is an overlap under the closed-interval contract.
Constraints
0 <= intervals.length <= 105intervals[i].length == 2-231 <= start <= end <= 231 - 1
Hints
Hint 1
What order makes potential overlap local?
Hint 2
After sorting, which already-merged interval can the next one touch?
Hint 3
Compare with the last end, append on a strict gap, otherwise extend with max.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Nested and touching groups
[[1,4],[2,3],[4,6],[8,8]]
[[1,6],[8,8]]