Merge Overlapping Intervals

You are given an array intervals where each intervals[i] = [start, end] denotes a closed interval on the number line.

Merge every group of intervals that overlap and return the resulting set of non-overlapping intervals that together cover exactly the same points as the input. Two intervals count as overlapping if they share at least one point, so intervals that merely touch at an endpoint (for example [1, 4] and [4, 5]) must be merged.

Return the merged intervals sorted in ascending order by start value.

Examples

Example 1

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Intervals [1,3] and [2,6] overlap, so they merge into [1,6]. The others are disjoint.

Example 2

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] touch at 4, which counts as overlapping, so they merge into [1,5].

Example 3

Input: intervals = [[4,7],[1,4]]
Output: [[1,7]]
Explanation: The input need not be sorted. [1,4] and [4,7] touch at 4 and merge into [1,7].