Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Meeting Rooms II
• Main tags: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue)

What the problem is really asking

Each interval represents one meeting with a start time and an end time.

The question is not really about building a calendar or labeling rooms. It is asking:

how many meetings are happening at the same time at the busiest moment?

That maximum overlap is exactly the number of rooms required.

If at some point three meetings overlap, then three rooms are necessary. If no moment ever has more than three active meetings, then three rooms are also sufficient.

Why assigning actual room numbers is unnecessary

A common first instinct is to simulate rooms directly:

1. sort meetings by start time
2. keep track of which room is free
3. assign each new meeting to some room or open a new one

That works, but the final answer only asks for the count, not the schedule itself.

Once that is clear, the problem becomes simpler. There is no need to remember which specific meeting went into which specific room. The only thing that matters is how many rooms are currently occupied as time moves forward.

The key insight

The answer is the peak number of active meetings.

There are two clean ways to compute that:

• sort meetings by start time and keep a min-heap of current end times
• separate all start times and end times, sort both lists, and sweep them with two pointers

Both approaches are O(n log n) because sorting dominates.

For this problem, the two-pointer sweep is usually the easiest final answer to explain because it focuses directly on overlap counting.

How to derive the two-pointer solution

Start by separating the intervals into two sorted lists:

• starts: every meeting start time, sorted ascending
• ends: every meeting end time, sorted ascending

Now imagine walking through meetings in the order they start.

Before counting a new meeting as active, first release every meeting that has already ended. That means moving the end pointer forward while:

ends[end_index] <= current_start

That <= matters. If one meeting ends at time 10 and another starts at time 10, they can reuse the same room, so those meetings do not overlap.

After releasing finished meetings:

1. add the current meeting
2. update the maximum number of active meetings seen so far

That maximum is the answer.

Why this is optimal

Any correct solution has to inspect every interval, and it also has to reason about time order. Sorting is the natural way to make that order explicit.

After sorting, the sweep itself is linear:

• each start time is processed once
• each end time is advanced once

So the total work is:

• O(n log n) time for sorting
• O(n) time for the scan

Overall, that is O(n log n) time with O(n) extra space for the sorted time lists.

A simple example

Suppose the meetings are:

[[0, 30], [5, 10], [15, 20]]

Then:

• starts = [0, 5, 15]
• ends = [10, 20, 30]

Sweep through the starts:

• start 0: no meeting has ended yet, so active rooms become 1
• start 5: still no meeting has ended, so active rooms become 2
• start 15: the meeting ending at 10 is already finished, so release one room first, then add the new meeting and stay at 2

The maximum active count is 2, so two rooms are needed.

Best solution choices

The two main answers worth knowing are:

• Two-pointer sweep: best when the task only asks for the number of rooms
• Min-heap of end times: best when the interviewer naturally thinks in terms of room reuse or later asks for actual room assignments

They have the same asymptotic runtime for this problem. The difference is mostly in what they make easiest to explain next.

Python solution

from typing import List, Sequence


class MeetingRoomCounter:
    """Compute the minimum number of rooms needed for a set of meetings."""

    def min_rooms_required(self, intervals: Sequence[Sequence[int]]) -> int:
        if not intervals:
            return 0

        sorted_start_times = self._sorted_start_times(intervals)
        sorted_end_times = self._sorted_end_times(intervals)

        active_room_count = 0
        max_room_count = 0
        end_index = 0

        for start_time in sorted_start_times:
            # Free every room whose meeting has already ended before this start.
            while end_index < len(sorted_end_times) and sorted_end_times[end_index] <= start_time:
                active_room_count -= 1
                end_index += 1

            active_room_count += 1
            max_room_count = max(max_room_count, active_room_count)

        return max_room_count

    def _sorted_start_times(self, intervals: Sequence[Sequence[int]]) -> List[int]:
        return sorted(interval[0] for interval in intervals)

    def _sorted_end_times(self, intervals: Sequence[Sequence[int]]) -> List[int]:
        return sorted(interval[1] for interval in intervals)


class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        counter = MeetingRoomCounter()
        return counter.min_rooms_required(intervals)

Why this works

The algorithm maintains a simple invariant:

after releasing ended meetings and before moving to the next start time, active_room_count equals the number of meetings currently in progress.

That invariant is true because:

• every meeting start increases the active count by one
• every meeting end that occurs on or before the next start decreases the active count by one

So during the sweep, active_room_count always matches the number of rooms currently occupied.

The required answer is the minimum number of rooms that can support the schedule. That is exactly the largest number of simultaneous meetings at any moment. Since max_room_count records the largest active count ever seen, it must be the correct answer.

Interview follow-ups

How would you solve it with a heap instead?

Sort the intervals by start time and keep a min-heap of end times for meetings currently using a room. For each new meeting, compare its start time with the smallest end time in the heap. If the earliest meeting has already ended, pop that end time because its room can be reused. Then push the current meeting’s end time. The heap size after each insertion is the number of rooms currently needed, and the maximum heap size over the whole scan is the answer. This works because the smallest end time is always the next room that could become available. The runtime is still O(n log n) overall, with O(n) space in the worst case. This version is especially useful when the interviewer later asks for actual room assignment logic.

What if the interviewer wants the actual room number assigned to each meeting?

Then the heap-based design becomes the better foundation. One min-heap can store available room numbers, and another can store busy rooms as (end_time, room_number). As meetings are processed in start-time order, rooms whose meetings have ended move back into the available-room heap. Each new meeting takes the smallest available room number, or opens a new room number if none is free yet. This gives both the minimum room count and a concrete assignment plan. The tradeoff is a bit more bookkeeping than the two-pointer solution, but the core idea is the same: always reuse the room that becomes available earliest.

What changes if meetings that touch at endpoints should count as overlapping?

The comparison rule changes. In the standard problem, a meeting ending at time t frees the room for another meeting starting at time t, so the release condition is end <= start. If touching meetings should instead be treated as overlapping, the release condition must become end < start. That single comparison changes the overlap model and can increase the answer by one in edge cases where many meetings meet exactly at boundaries. The algorithmic structure does not change, but getting this detail wrong changes the meaning of the schedule.

What if meetings arrive online in sorted start-time order?

The heap solution adapts naturally to that setting. Keep a min-heap of end times as persistent state. For each arriving meeting, pop every end time that is less than or equal to the new start time, then push the new end time. The maximum heap size seen so far is the number of rooms required for everything processed up to that point. This remains O(log n) amortized work per meeting after the stream begins. The two-pointer method is better for a fixed offline batch, while the heap version is better when new meetings keep arriving over time.

Practical takeaway

The easiest way to see this problem clearly is to stop thinking about rooms first and think about overlap first.

Once the question is reframed as “what is the largest number of meetings happening at once?”, the solution becomes a standard sweep-line count. That viewpoint is simpler, easier to justify in an interview, and directly leads to the optimal answer.