Meeting Rooms II

You are given a list of meetings intervals, where intervals[i] = [start, end] means meeting i occupies a room from time start up to, but not including, time end.

A room can host only one meeting at a time. Because a meeting releases its room at its end time, a meeting ending at time t and another starting at time t can use the same room.

Return the smallest number of rooms needed so that every meeting can take place. The meetings are not given in any particular order.

Example 1

Input: intervals = [[1,6],[12,15],[4,9],[5,8]] Output: 3 Why: At time 5 three meetings are running at once ([1, 6], [4, 9] and [5, 8]), so 3 rooms are needed. The meeting [12, 15] can reuse any of them.

Example 2

Input: intervals = [[3,7],[7,10]] Output: 1 Why: The second meeting starts exactly when the first ends, so one room is enough.

Example 3

Input: intervals = [[2,11]] Output: 1 Why: A single meeting needs one room.

Constraints

  • 1 <= intervals.length <= 104
  • 0 <= start < end <= 106

Pattern Path · Intervals & Greedy · problem 116 of 169

The answer is the largest number of meetings that are running at the same moment. Why is that enough, and why is it necessary?
Process meetings in order of start time. When a new meeting starts, which room should it try to reuse?
Either keep a min-heap of end times of rooms in use, or sort all starts and all ends separately and sweep through them with two pointers, counting how many meetings are open.
Target: O(n log n) time, O(n) extra space.

Start simple

For every meeting start, count how many meetings are running at that moment and take the maximum: O(n²) time.

The key idea

At any instant the rooms in use must be at least the number of meetings running then, so the answer is at least the maximum overlap. Assigning rooms greedily by start time never needs more than that, so the answer is exactly the maximum overlap.

To measure it, note that only the times matter, not which start pairs with which end. Sort the start times and the end times into two separate lists and sweep with two pointers, like walking along a timeline:

  • If the next event is a start that comes before the next end, a new meeting opens: increase the open count.
  • Otherwise the earliest-ending meeting has finished, so its room is free: move the end pointer and decrease the count.

When a start and an end share the same time, process the end first; that is how a room is reused by back-to-back meetings. The largest open count seen during the sweep is the answer.

An equivalent method sorts meetings by start and keeps a min-heap of end times: if the earliest end is at or before the new start, reuse that room; the heap's final size is the answer.

Complexity

  • Time: O(n log n)
  • Space: O(n)

Python

class Solution:
    def minMeetingRooms(self, intervals):
        starts = sorted(s for s, _ in intervals)
        ends = sorted(e for _, e in intervals)
        rooms = best = 0
        j = 0                          # next meeting end to process
        for start in starts:
            # Free every room whose meeting has ended by this start (end == start counts as free).
            while ends[j] <= start:
                rooms -= 1
                j += 1
            rooms += 1
            best = max(best, rooms)
        return best

JavaScript

var minMeetingRooms = function(intervals) {
  const starts = intervals.map(([s]) => s).sort((a, b) => a - b);
  const ends = intervals.map(([, e]) => e).sort((a, b) => a - b);
  let rooms = 0, best = 0, j = 0;   // j = next meeting end to process
  for (const start of starts) {
    // Free every room whose meeting has ended by this start (end == start counts as free).
    while (ends[j] <= start) {
      rooms--;
      j++;
    }
    rooms++;
    best = Math.max(best, rooms);
  }
  return best;
};

What the interviewer is checking

It tests whether you can turn a scheduling question into "maximum overlap" and choose an efficient sweep or heap, including the boundary rule for touching intervals.

Mistakes to avoid

  • Treating a meeting that starts exactly when another ends as overlapping (handle ends before starts at equal times).
  • Sorting intervals by start and only comparing neighbours, which misses overlaps with earlier, longer meetings.
  • Pairing each start with its own end in the two-list sweep; the lists are sorted independently on purpose.
  • Forgetting that the input is unsorted.

Follow-ups to expect

  • Can you report which room each meeting gets? (Heap of (end, roomId).)
  • Can one person attend every meeting? (Sort by start, check neighbours.)
  • What if times are small integers? (Difference array plus prefix sums.)

In real software

Calendar room booking, counting concurrent sessions or connections, and sizing a worker pool for overlapping jobs all compute peak overlap this way.

Practice next

Next Post Previous Post
No Comment
Add Comment
comment url