1102. Busiest Start Time
A co-working space rents out one shared meeting room. Each booking in intervals is a pair [begin, length]: the guests walk in at minute begin and the room is theirs for exactly length minutes, so it is occupied at the minutes begin, begin + 1, ..., begin + length - 1. At minute begin + length the room is already free for someone else.
Since all bookings use the same room, the manager wants to know when the overlap is worst. Return the earliest whole minute t at which the number of bookings occupying the room at the same moment is as large as it ever gets. Bookings are listed in no particular order, and several may share a begin minute.
Example 1
- Input:
- intervals = [[2,4],[3,2],[5,3],[9,1]]
- Output:
- 3
- Explanation:
The room holds two bookings at minutes 3 and 4 (and again at 5), so the earliest busiest minute is 3.
Example 2
- Input:
- intervals = [[1,1],[2,1],[3,1]]
- Output:
- 1
- Explanation:
The bookings never overlap, so every minute has one booking and the earliest, 1, is returned.
Constraints
1 ≤ intervals.length ≤ 105
intervals[i] = [begin, length]
1 ≤ begin, length ≤ 106
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)