Coding · Intervals
Minimum Meeting Rooms
- Reported once
- Medium
- SDE-2 (2-3 years)
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
Meetings are given as [start, end] pairs with the start before the end, in no particular order. Two meetings clash when they overlap in time, and a meeting that ends at the very moment another begins does not clash with it. Return the fewest rooms that can hold all the meetings. For [[0,30],[5,10],[15,20]] the answer is 2. There are up to 100,000 meetings and times go up to two billion.
Restated in our own words, not a quote from Razorpay or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
The candidate report was posted in 2020 and describes an SDE-2 first round in which the interviewer wanted the brute force first and the optimised version coded while explaining. It gives only a link to the InterviewBit Meeting Rooms problem, which asks for the fewest conference rooms and lets a meeting start in the room another just left, so that is the version solved here. I would plan to say both approaches aloud. Before coding I would ask: does a meeting that ends exactly when another starts clash? (No, they can share a room.) Is every start strictly before its end? Is the input sorted? Do I return only the number of rooms or also the assignment? How many meetings are there?
Assumptions I would state: start is strictly before end, the order is arbitrary, touching meetings can share a room, times are integers, and only the count is returned.
Brute force
Say the obvious answer and why it is too slow.
The most crowded moment always coincides with the start of some meeting. So for every meeting, take its start time and count how many meetings are running at that instant, meaning start at or before it and end after it. The largest count is the number of rooms. Counting is a pass over all meetings, and doing it for every meeting is O(n²), about ten billion steps at 100,000 meetings.
Another direct method keeps a list of rooms and tries each meeting against each room in turn. It is correct as well, but it costs O(n times the number of rooms) and needs the meetings sorted by start first. Both repeat work that sorting removes.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n²)
- Time
- O(n log n)
- Space
- O(n)
The pattern is sort the starts and the ends separately and sweep. The answer is the largest number of meetings running at once, so we only need to know, whenever a meeting starts, whether some earlier meeting has already finished. Sort all start times, and sort all end times in a second array. Walk through the starts in order with a pointer into the ends that marks the earliest end not yet used to free a room.
For each start, compare it with that earliest end. If the start is at or after it, that meeting is over, so its room is free: reuse it and advance the pointer. Otherwise every meeting begun so far is still running, so a new room is needed: add one. The count of rooms added is the answer.
Why can we forget which end belongs to which meeting? Every meeting ends after it starts. An end time at or before the current start therefore belongs to a meeting that began even earlier, and starts are processed in order, so that meeting has already been counted. What matters is only how many meetings have finished, not which ones.
Why is the room count right even though the pointer moves at most one step per start? Rooms are only ever added, never removed, so the count never drops. The pointer never gets ahead of the number of ends at or before the current start. A room is added only when the pointer has caught up with all of those ends. At that moment the rooms equal the meetings started minus the meetings finished, which is the true crowd at that start. The busiest moment is the start of some meeting, so the final count equals the peak.
Touching meetings share a room because the comparison is greater-or-equal. The usual alternative is a min-heap of end times with the same O(n log n) cost: pop the earliest end if it is at or before the new start, push the new end, and track the largest heap size.
Out loud: "I line up all the starts and all the ends in order. Each start either reuses the earliest finished room or opens a new one."
Walk it through
A dry run on the example, step by step.
| Start | Earliest end | Reuse? | Rooms |
|---|---|---|---|
| 1 | 4 | no | 1 |
| 2 | 4 | no | 2 |
| 3 | 4 | no | 3 |
| 4 | 4 | yes | 3 |
| 8 | 5 | yes | 3 |
Take [[1,4],[2,5],[3,6],[4,7],[8,9]]. The sorted starts are 1, 2, 3, 4, 8 and the sorted ends are 4, 5, 6, 7, 9. Start 1 meets the earliest end 4: not over yet, so rooms = 1. Start 2 also meets 4, so rooms = 2, and start 3 gives rooms = 3.
Start 4 meets the earliest end 4, and 4 is at or after 4, so the first meeting has just finished and its room is reused, which advances the end pointer to 5. Start 8 is after 5, so another room is reused. No new room was needed for the last two, so the answer is 3.
The code
Runnable JavaScript, checked against test cases.
function minMeetingRooms(intervals) {
const starts = intervals.map((meeting) => meeting[0]).sort((a, b) => a - b);
const ends = intervals.map((meeting) => meeting[1]).sort((a, b) => a - b);
let rooms = 0;
let freed = 0;
for (const start of starts) {
if (start >= ends[freed]) freed++;
else rooms++;
}
return rooms;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
No meetings: both arrays are empty and the answer is 0.
- Touching meetings: [1,5] and [5,10] share one room because the test is greater-or-equal.
- Identical meetings: three copies of [1,5] need three rooms.
- One meeting containing the rest: [1,10] with [2,3] and [4,5] needs two rooms, not three, since the short ones do not overlap each other.
- Unsorted input: the code sorts copies of the starts and ends, so the input order does not matter and the input is not changed.
- Zero-length meetings: not supported, because the first rule assumes start is strictly before end. A [5,5] alone would count no room, so state the assumption.
- Times with different digit counts: they need a numeric comparator in the sort, because the default sort compares text.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return which meeting is in which room, and what would the heap hold instead of just end times?
- How is the minimum number of platforms for trains with arrival and departure times the same problem, and where does the tie rule at equal times change the answer?
- How would you solve it if meetings arrive one at a time and the count must be available after each arrival?
- How would you find the largest number of non-overlapping meetings that fit in a single room?
- How would you report the time window in which the largest overlap occurs?
Where candidates slip
The mistakes this problem punishes.
In JavaScript the biggest slip is calling sort without a comparator. The default sorts numbers as text, so 10 comes before 2 and every answer is wrong for times of different lengths. Always pass (a, b) => a - b.
- Using a strict comparison, which counts meetings that only touch as clashing and returns too many rooms.
- Sorting only the starts and leaving the ends in input order, so the earliest end is not at the front.
- Confusing it with the easier question of whether one person can attend all meetings, which only asks whether any overlap exists.
- Mutating the caller's input array by sorting it in place.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.