Merge Intervals

You get a vector 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 a vector 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.