Merge Overlapping Intervals

Given an array intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Two intervals are considered overlapping if they share at least one point, so an interval ending at 5 and one starting at 5 (e.g. [1, 5] and [5, 8]) should be merged into [1, 8]. The input intervals are not guaranteed to be sorted or disjoint.

Example 1

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

Example 2

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: [1, 4] and [4, 5] touch at 4, so they are merged.

Constraints

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^5