Merge Intervals

Each element of intervals is a pair [start, end] with start ≤ end. Merge every set of intervals that overlap, and return the merged intervals sorted by their start. Intervals that only touch, such as [1, 4] and [4, 5], overlap too.

Constraints

  • 1 ≤ number of intervals ≤ 4,000
  • 0 ≤ start ≤ end ≤ 1,000,000

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 become [1, 6].

Example 2

Input
intervals = [[1,4],[4,5]]
Output
[[1,5]]
Why:

Intervals that touch merge.

Example 3

Input
intervals = [[5,7],[1,2]]
Output
[[1,2],[5,7]]
Why:

No overlap, but the answer is sorted by start.

Hints

    Was this a good challenge?

    Solved by
    0
    Submissions
    0
    Accepted
    –