Merge Intervals

We are given an array of closed intervals, intervals, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval. Your task is to merge the overlapping intervals and return a new output array consisting of only the non-overlapping intervals.

Statement

We are given an array of closed intervals, intervals, where each interval has a start time and an end time. The input array is sorted with respect to the start times of each interval. For example, intervals = [[1,4], [3,6], [7,9]] is sorted in terms of start times 1, 3, and 7.

Your task is to merge the overlapping intervals and return a new output array consisting of only the non-overlapping intervals.

Constraints

• 1 ≤ intervals.length ≤ 10⁴
• intervals[i].length = 2
• 0 ≤ start time ≤ end time ≤ 10⁴

Examples

Example 1

Input Intervals: [1, 5], [3, 7], [4, 6], [6, 8]

Explanation: Intervals [1, 5], [3, 7], [4, 6], [6, 8] are overlapping. Merge them into one interval [1, 8].

Output: [1, 8]

Example 2

Input Intervals: [10, 12], [12, 15]

Explanation: Intervals [10, 12], [12, 15] are overlapping. Merge them into one interval [10, 15].

Output: [10, 15]

Example 3

Input Intervals: [1, 3], [2, 6], [8, 10], [15, 18], [18, 20]

Explanation:

• Intervals [1, 3] and [2, 6] overlap and are merged to [1, 6].
• Intervals [15, 18] and [18, 20] overlap and are merged to [15, 20].

Output: [1, 6], [8, 10], [15, 20]