Merge Intervals

Merge Intervals

Given an array of 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 [a, b] and [c, d] overlap if c <= b (the second starts before or when the first ends). When they overlap, they merge into [min(a,c), max(b,d)].

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].

Example 2:

Input: intervals = [[1, 4], [4, 5]]
Output: [[1, 5]]
Explanation: Intervals [1,4] and [4,5] touch at boundary 4, so they merge into [1,5].

Example 3:

Input: intervals = [[1, 4], [0, 4]]
Output: [[0, 4]]
Explanation: After sorting by start: [0,4] and [1,4] overlap and merge into [0,4].

Constraints

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

Expected Complexity

• Time: O(n log n). dominated by sorting
• Space: O(n). for the output array