An office has a list of meetings to host, intervals, where intervals[i] = [startᵢ, endᵢ] means a meeting runs from time startᵢ up to time endᵢ. A room can host one meeting at a time.
Return the fewest rooms that can host every meeting. A room becomes free the moment its meeting ends, so a meeting that starts at time t can use the room of one that ends at t.
At time 8 three meetings are running at once: [2,9], [7,12] and [8,10], so three rooms are needed. [4,6] is over by then, and it can share a room with [7,12].
In time order the meetings are [1,5], [5,9] and [9,11]. Each one starts just as the one before it ends, so a single room hosts all three back to back.
From 15 to 20 the meetings [0,100], [10,20] and [15,25] all run at once. By 30 the last two are over, so [30,40] can take either of their rooms.
Constraints
1 <= intervals.length <= 10⁴intervals[i].length == 20 <= startᵢ < endᵢ <= 10⁶The number of rooms you need is the largest number of meetings running at the same moment. That moment always falls at some meeting's start.
Freeze the clock at any moment and count the meetings in progress. If five are running, you need at least five rooms, because no room holds two meetings at once. So the answer can't be smaller than the busiest moment.
Time O(n log n)Space O(n)
The full walkthrough and code are part of Premium
3