A strong answer
The minimum number of rooms equals the maximum number of meetings in progress at any single moment: that many are clearly needed, and greedily reusing any free room never needs more.
Sweep: turn each meeting [start, end) into a +1 event at start and a −1 event at end, sort by time with ends before starts at equal times (so a room freed at 10 can be reused at 10), and walk the events keeping a running count. The largest count is the answer. Sorting dominates: O(n log n).
Heap: sort meetings by start. Keep a min-heap of end times of meetings currently holding rooms. For each meeting, if the earliest end in the heap is at or before its start, that room is free: pop it. Push the meeting's end. The heap's maximum size, which is its final size here, is the number of rooms. Also O(n log n), and it naturally extends to assigning rooms: store (end, room id) and reuse the popped room's id.
If times are small integers, such as minutes in a day, a difference array indexed by time replaces sorting: +1 at each start, −1 at each end, and the maximum prefix sum is the answer in O(n + T).
The tie rule depends on the interval convention: for half-open intervals, touching meetings don't conflict; for closed ones, they do, and starts must be processed before ends.
What the interviewer is listening for
- The reduction to maximum overlap, with a reason it is optimal.
- One correct O(n log n) solution with ties handled deliberately.
- Awareness of the heap version for room assignment, and of the integer-time shortcut.
Common mistakes
- Comparing all pairs of meetings.
- Getting the tie order wrong, which overcounts rooms by one.
- Sorting by end time for this problem, which doesn't give the overlap count.