Merge Intervals

Each interval is [start, end] with start <= end. Merge every group of intervals that overlap or touch (for example [1, 3] and [3, 5] touch at 3) into one interval, and return the merged intervals sorted by start. Intervals that only come close without touching ([1, 2] and [3, 4]) stay separate.

Examples

Example 1

Input:

merge_intervals([[1, 3], [8, 10], [2, 6], [15, 18]])

Output:

[[1, 6], [8, 10], [15, 18]]

[1, 3] and [2, 6] overlap and merge into [1, 6].

Example 2

Input:

merge_intervals([[1, 4], [4, 5]])

Output:

[[1, 5]]

They touch at 4, so they merge into [1, 5].

Constraints

• 0 <= len(intervals) <= 2 * 10**5
• 0 <= start <= end <= 10**9
• The intervals are in any order.