Merging Ranges

mediumSave

ArrayIntervalsSorting

Given an array of intervals where each interval is a pair of integers representing a start and an end time, write a function that merges all overlapping intervals. The function should return the merged intervals in ascending order.

Example 1

Input

Output

[[1, 6], [8, 10], [15, 18]]

Explanation. Intervals [1, 3] and [2, 6] are overlapping and should be merged into [1, 6]. The others do not overlap.

Example 2

Input

Output

[[1, 5]]

Explanation. Intervals [1, 4] and [4, 5] are touching and should be merged into [1, 5].

Example 3

Input

Output

[[1, 9]]

Explanation. All intervals overlap with each other in some way and can be merged into a single interval [1, 9].

Follow-up: Can you improve your algorithm to operate in `O(n log n)` time complexity?

Constraints:

- Each pair in the array will represent an interval with a start time and an end time. - The start time will always be less than or equal to the end time. - Intervals are represented as arrays with two integer elements: `[start, end]`.

Views: 3