Meeting Rooms II
eBay● MediumFULLTIMEPHONE SCREENProblem statement
You are given an array of meeting time intervals, intervals, where intervals[i] = [starti, endi]. Return the minimum number of conference rooms required so that every meeting has a room for its whole time.
A meeting uses its room from starti up to, but not including, endi. So a room freed at time t can host a meeting that starts at t. The intervals can come in any order.
Interview follow-ups
These two follow-ups came up as discussion. They are not part of the judged function, and the editorial covers them.
- Dynamic stream: what if meetings arrive as a continuous stream instead of a static array, and you need to check instantly whether a new meeting fits?
- Room constraints: what if rooms have different capacities and meetings have different people counts, so a meeting cannot go into just any room?
Function
minMeetingRooms(intervals: int[][]) → intExamples
Example 1
intervals = [[0,30],[5,10],[15,20]]return = 2The meeting [0,30] overlaps both others, but [5,10] and [15,20] do not overlap each other, so they can share one room. Two rooms are enough.
Example 2
intervals = [[7,10],[2,4]]return = 1The input is not sorted. The meeting [2,4] ends before [7,10] starts, so one room is enough.
Example 3
intervals = [[1,5],[5,9],[9,12],[4,6]]return = 2The meetings [1,5], [5,9] and [9,12] run back to back and can share a room, because a room freed at time t can host a meeting that starts at t. The meeting [4,6] overlaps [1,5] and [5,9], so it needs a second room.
Constraints
1 <= intervals.length <= 5000intervals[i].length == 20 <= starti < endi <= 10^6