1372. Free Gaps in the Day
A clinic keeps one shared calendar for a single day that runs from minute 0 up to, but not including, minute dayEnd. Each entry meetings[i] = [start, end) blocks that room from start up to but not including end. The entries arrive in no particular order and may overlap or sit inside each other.
Return every maximal stretch [a, b) with a < b inside [0, dayEnd) that no meeting touches, listed in ascending order of a. Two meetings where one ends exactly when the next begins leave no gap between them. If the whole day is booked, return an empty list.
Sort by start, sweep once while tracking how far the booked time reaches, and report each hole. Target O(n log n) time and O(n) space for the output.
Example 1
- Input:
- meetings = [[9,12],[1,3],[2,5]], dayEnd = 15
- Output:
- [[0,1],[5,9],[12,15]]
- Explanation:
Booked time is [1,5) and [9,12), so the free stretches are [0,1), [5,9) and [12,15).
Example 2
- Input:
- meetings = [[0,4],[4,8]], dayEnd = 8
- Output:
- []
- Explanation:
The meetings touch at 4 and cover the whole day, so there is no gap.
Example 3
- Input:
- meetings = [[3,5]], dayEnd = 10
- Output:
- [[0,3],[5,10]]
- Explanation:
One meeting leaves [0,3) before it and [5,10) after it.
Constraints
- 1 ≤ n ≤ 200, where n is the number of meetings
- 0 ≤ start < end ≤ dayEnd ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)