#219MediumIntervals· Merging Intervals to Find Gaps

Free Slots Between Bookings

A workshop is open from time `0` to time `dayLength` and customers book the machine for half-open slots `[start, end)`. The bookings arrive in no particular order and may overlap, because several customers can share the machine at once. Return every period during which nobody has booked the machine. Each free period is a half-open interval `[start, end)` of positive length inside `[0, dayLength)`, and the periods must be listed from earliest to latest. Free periods touching each other cannot happen: two bookings that merely touch (one ends when the next starts) leave no gap between them.

Input format

`dayLength`: the closing time; `bookings`: an array of `[start, end]` pairs.

Output format

An array of `[start, end]` pairs: the free periods in ascending order (an empty array when the day is fully booked).

Examples

Input: dayLength = 10, bookings = [[2, 4], [3, 6], [8, 9]]

Output: [[0, 2], [6, 8], [9, 10]]

The first two bookings overlap and together occupy 2 to 6. The free time is 0 to 2, 6 to 8 and 9 to 10.

Input: dayLength = 5, bookings = []

Output: [[0, 5]]

With no bookings the whole day is free.

Input: dayLength = 6, bookings = [[3, 6], [0, 3]]

Output: []

The bookings touch at time 3 and together cover the whole day, so nothing is free.

Constraints

1 <= dayLength <= 10^9
0 <= bookings.length <= 10^5
0 <= start < end <= dayLength

#intervals
#sorting
#merge
#sweep-line