Merge Intervals

Medium·Tagsarraysorting

Problem Statement

Given a list of intervals, merge all the overlapping intervals to produce a list that has only mutually exclusive intervals. Each interval is represented as a pair of numbers `[start, end]`, where `start <= end`.

Examples

Example 1

Input

intervals: [[1, 4], [2, 5], [7, 9]]

Timeline

Output

"[[1, 5], [7, 9]]"

Why

Since the first two intervals [1, 4] and [2, 5] overlap, we merged them into one [1, 5].

Example 2

Input

intervals: [[6, 7], [2, 4], [5, 9]]

Timeline

Output

"[[2, 4], [5, 9]]"

Why

Since the intervals [6, 7] and [5, 9] overlap, we merged them into one [5, 9].

Example 3

Input

intervals: [[1, 4], [2, 6], [3, 5]]

Timeline

Output

"[[1, 6]]"

Why

Since all the given intervals overlap, we merged them into one.

Constraints

•1 <= intervals.length <= 10000
•intervals[i].length == 2
•0 <= start <= end <= 10000

Hints

Stuck? Reveal a nudge toward the right pattern, one step at a time.

Hint 1

If the intervals are completely scrambled, it will be very difficult to know if an interval overlaps with another one without comparing it to every single interval in the list.

Hint 2

Sort the intervals on the start time to ensure that `a.start <= b.start`.

Hint 3

If the intervals are sorted by start time, two intervals `a` and `b` will overlap if `b.start <= a.end`.

Hint 4

When merging overlapping intervals, the new interval will have the start of `a` and the end of `max(a.end, b.end)`.