Merge Booking Windows

Given a list of booking windows as [start, end] pairs, merge all overlapping or touching windows and return the merged windows sorted by start. Two windows overlap or touch if one's start is <= the other's end.

Examples

in: intervals = [[1,3],[2,6],[8,10],[15,18]]

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

[1,3] and [2,6] merge

in: intervals = [[1,4],[4,5]]

out: [[1,5]]

touching windows merge

Constraints

0 <= len(intervals) <= 10^4
start <= end
0 <= start, end <= 10^9

Hints

target: O(n log n) time⌘↩ run · ⇧⌘↩ submit