All problems

Common Free Time

Medium · intervals

Several people share a calendar. You are given busy, a list of rows [person, start, end]: the person numbered person is busy from time start up to, but not including, time end. So a person who is busy during [1, 3) and then [3, 5) is busy without a break from 1 to 5.

The rows come in any order and different people may be busy at the same time. The only promise is about a single person: that person's rows, in the order they appear in busy, go forward in time and never overlap each other (one may end exactly where the next begins).

Return every stretch of time [from, to] where nobody is busy, from < to, and which lies between the earliest start and the latest end of all the rows. Time before everyone's first start and after everyone's last end does not count. Return the stretches in increasing order, so that each one ends before the next begins. If there is no such stretch, return an empty list.

Examples

Example 1

Input: busy = [[0, 1, 3], [0, 6, 7], [1, 2, 4], [2, 5, 6]]

Output: [[4, 5]]

Together the three people are busy from 1 to 4, and from 5 to 7. Only the time from 4 to 5 is free for everybody.

Example 2

Input: busy = [[0, 1, 4], [1, 4, 9], [0, 12, 15], [1, 11, 12]]

Output: [[9, 11]]

Person 0 stops at 4 exactly when person 1 starts, so there is no gap there. Nobody is busy from 9 to 11.

Example 3

Input: busy = [[3, 0, 10]]

Output: []

One long block leaves nothing free between the earliest start and the latest end.

Constraints