70. Merge Intervals

Given an array of intervals 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.

Input: A 2D array intervals where intervals[i]=[start,end].

Output: Array of merged non-overlapping intervals sorted by start.

Examples

Input: [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: [1,3] and [2,6] overlap → merge to [1,6]. [8,10] and [15,18] don't overlap.

Input: [[1,4],[4,5]]
Output: [[1,5]]
Explanation: [1,4] and [4,5] touch at 4 → merge to [1,5].

Input: [[1,4],[2,3]]
Output: [[1,4]]
Explanation: [2,3] is contained within [1,4].

Constraints

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

Asked by