Loading page…
Practice problem · medium
A bank app lets customers book appointments with advisors in the rooms of a branch. Each appointment is a pair [start, end) in minutes. The room is in use from the start minute up to, but not including, the end minute.
An appointment can use a room that another appointment has left, including one that ends at the very minute the new one starts. The branch wants to know how many rooms it must have so that every appointment gets a room.
Write rooms_needed(meetings).
meetings[i] = [start, end), with start < end. The meetings are in no particular order.Input: meetings = [[0, 30], [5, 10], [15, 20]]
Output: 2Sort the start times and the end times separately. Go through the starts. A meeting reuses a room when the earliest end is at or before its start. Otherwise it needs a new room.
| Start | Earliest unused end | Reuse a room? | Rooms |
|---|---|---|---|
| 0 | 10 | no, 0 < 10 | 1 |
| 5 | 10 | no, 5 < 10 | 2 |
| 15 | 10 | yes, 10 ≤ 15: that room is reused | 2 |
Two rooms are enough.
Input: meetings = [[0, 5], [5, 10]]
Output: 1The first meeting ends at minute 5 and the second starts then. They can share one room.
Input: meetings = [[0, 10], [1, 2], [3, 4], [5, 6]]
Output: 2The long meeting always needs a room, and the three short ones never overlap each other, so they can share a second room.
0 ≤ meetings.length ≤ 100,0000 ≤ start < end ≤ 1,000,000,000 (minutes)Counting how many meetings are running at each start time, by checking all the meetings, costs about n × n, which is 10^10 at n = 100,000. Sorting the starts and the ends costs n log n, and one pass costs n.
rooms_needed · runs in your browserCoding is easiest on a laptop. On a phone, read, trace and try small edits.