Compute minimum required meeting rooms
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
Given a list of meeting time intervals [start, end) for many events, determine the minimum number of rooms required so no meetings overlap in the same room. Describe and implement an algorithm using a min-heap of end times, explain its time and space complexity, and compare it with a sweep-line approach using sorted start/end times. Specify how you would handle edge cases such as zero-length meetings, identical start and end times across meetings, and very large input sizes.
Quick Answer: This question evaluates understanding of interval scheduling and resource-allocation concepts, proficiency with data structures for detecting temporal overlaps (heap and sweep-line paradigms), and the ability to analyze time and space complexity while handling edge cases.
Given a list of meeting time intervals `[start, end)` (half-open: a meeting ending at time `t` does NOT conflict with one starting at `t`), return the minimum number of conference rooms required so that no two overlapping meetings share a room.
Approach (min-heap of end times): sort meetings by start time. Maintain a min-heap of the end times of meetings currently occupying rooms. For each meeting, if the earliest-freeing room (heap top) has ended at or before the new meeting's start, reuse that room (pop + push the new end); otherwise allocate a new room (push). The answer is the maximum heap size reached, which equals the final heap size after processing all meetings.
Complexity: O(n log n) time (sort + heap ops), O(n) space. A sweep-line alternative sorts start and end times separately and walks both pointers, incrementing a counter on a start and decrementing on an end (process ends before equal starts to honor the half-open interval), tracking the running max — same O(n log n) time, O(n) space, no heap.
Edge cases: zero-length meetings `[t, t]` occupy no time and never force an extra room when handled with `<=`; identical start/end times across meetings are handled by the half-open `end <= start` reuse check; very large inputs stay O(n log n) and the heap holds at most the peak concurrency.
Constraints
- 0 <= intervals.length <= 10^5
- intervals[i].length == 2
- 0 <= start_i <= end_i <= 10^9
- Intervals are half-open [start, end): a meeting ending at t does not conflict with one starting at t
- Zero-length meetings [t, t] are allowed
Examples
Input: [[0, 30], [5, 10], [15, 20]]
Expected Output: 2
Explanation: [0,30) overlaps both [5,10) and [15,20). [5,10) and [15,20) don't overlap each other, so they can share the second room sequentially. Peak concurrency = 2.
Input: [[7, 10], [2, 4]]
Expected Output: 1
Explanation: [2,4) ends before [7,10) starts, so the single room is reused. 1 room suffices.
Hints
- Sort the meetings by start time so you process them in chronological order.
- Track only the END times of meetings currently occupying rooms; the earliest end time is all you need to decide whether a room frees up.
- A min-heap gives the earliest-freeing room in O(log n). If heap top <= current start, reuse that room (heapreplace); otherwise push a new room.
- The minimum number of rooms equals the peak number of simultaneously overlapping meetings, which is the maximum heap size — and since rooms are never removed once the peak is reached only by net additions, the final heap size equals that peak.