Meeting Rooms Problems in Coding Interviews: Sort, Then Sweep
The "meeting rooms" family is a favorite at big tech phone screens. The questions look different, but they all reduce to sorting intervals and sweeping through time.
Meeting Rooms I: can one person attend everything?
Sort by start time, then check whether any meeting starts before the previous one ends. O(n log n) for the sort, O(1) extra space. Ask whether a meeting ending at 10:00 conflicts with one starting at 10:00; usually it does not.
Meeting Rooms II: minimum number of rooms
Two clean approaches, and interviewers like hearing both:
Min-heap of end times. Sort by start. For each meeting, pop the heap if the earliest end is at or before this start, then push this meeting's end. The heap size at the end is the answer.
Two sorted arrays. Sort starts and ends separately and walk both with pointers. Every start increases the count; every end that has passed decreases it. Track the maximum.
Follow-ups to expect
Return which room each meeting goes to (keep room ids in the heap).
Find free time slots shared by everyone (merge all busy intervals, then read the gaps).
Stream of meetings arriving online (the heap version adapts naturally).
How to present it
Draw a timeline with three or four overlapping meetings before coding. It makes the sweep obvious and shows the interviewer you checked edge cases. For timed practice on interval problems with spoken feedback, I use Linkjob AI interview assistant.
Disclosure: I work on Linkjob AI.
Comments