#184MediumGreedy· Merging Intervals

Merge Maintenance Windows

Different teams have announced maintenance windows for the same cluster. A window `[start, end]` means the cluster is down from minute `start` to minute `end` inclusive. Operations wants a clean public notice, so overlapping windows have to be merged into one. Two windows overlap if they share at least one minute, so `[1, 4]` and `[4, 5]` are merged into `[1, 5]`, but `[1, 4]` and `[5, 6]` are not. Given the list of announced windows in arbitrary order, return the merged windows sorted by start time. No two windows in the result may overlap.

Input format

`windows`: an array of pairs `[start, end]` with `start <= end`.

Output format

An array of merged, non-overlapping windows sorted by start.

Examples

Input: windows = [[1, 3], [8, 10], [2, 6], [15, 18]]

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

[1, 3] and [2, 6] overlap and become [1, 6]. [8, 10] and [15, 18] stand alone.

Input: windows = [[1, 4], [4, 5]]

Output: [[1, 5]]

The windows share minute 4, so they are merged into [1, 5].

Input: windows = [[5, 6], [1, 10], [2, 3]]

Output: [[1, 10]]

The window [1, 10] contains both of the others, so only [1, 10] remains.

Constraints

1 <= windows.length <= 10^4
0 <= start <= end <= 10^6

Study first

#intervals
#sorting
#greedy
#arrays