Merge Intervals

You get an array of intervals. Each interval is a pair [starti, endi]. It covers every point from its start to its end.

Merge the intervals that overlap. Return an array of the intervals you end up with, sorted by start.

Two intervals overlap if they share at least one point. Intervals that only touch count too. For example, [2,5] and [5,6] share the point 5. They become [2,6].

Example 1:

Input: intervals = [[5,8],[1,3],[7,11],[13,14]]
Output: [[1,3],[5,11],[13,14]]
Explanation: The input is not sorted.
[5,8] and [7,11] share 7 and 8.
They become [5,11].
[1,3] and [13,14] overlap no other interval.

Example 2:

Input: intervals = [[2,5],[5,6],[9,9]]
Output: [[2,6],[9,9]]
Explanation: [2,5] and [5,6] touch at 5.
That is enough to merge them.
[9,9] is a single point.
It stays on its own.

Example 3:

Input: intervals = [[3,20],[4,6],[10,12]]
Output: [[3,20]]
Explanation: [4,6] and [10,12] lie inside [3,20].
All three merge into [3,20].
It ends at 20, not at 12.

Constraints:

• 1 to 100,000 intervals, in any order.
• Each start and end is a whole number from 0 to 1,000,000.
• No start is greater than its end.