Module 4 · Scheduling Pattern

Meeting Rooms II

MediumProblem 7 of 14 8 min read ~20 min to solve LeetCode

HeapPriority QueueGreedySortingIntervals

Asked atAmazonGoogleMicrosoftMetaBloomberg

Problem Statement

Given an array of meeting time intervals where each interval has a start and end time, return the minimum number of conference rooms required so every meeting can happen without overlap.

Input

An integer matrix intervals, where intervals[i] = [starti, endi] represents one meeting.

Output

An integer: the minimum number of rooms needed to host all meetings.

Constraints

•1 <= intervals.length <= 10^4
•0 <= starti < endi <= 10^6

Examples

Example 1

Input:

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

Output: 2

Explanation: The meeting from 0 to 30 overlaps both shorter meetings, but the meetings from 5 to 10 and 15 to 20 can reuse the same second room.

Example 2

Input:

intervals = [[7,10],[2,4]]

Output: 1

Explanation: After sorting by start time, the meeting ending at 4 finishes before the meeting starting at 7, so one room is enough.

Learning Objectives

Recognise interval scheduling as a resource-reuse problem.
Use a min-heap of end times to find the room that frees earliest.
Explain why sorting by start time makes a single left-to-right scan valid.
Connect heap size with the number of rooms allocated so far.

Intuition

Pattern Recognition

The signal is meetings, rooms, intervals, or any schedule where a resource can be reused only after its current job ends. We do not need to compare the new meeting against every room. We only need the room that frees earliest, because if even that room is still busy, every other allocated room is also busy.

A min-heap gives exactly that earliest end time at the root. Sort meetings by start time, then let the heap represent rooms already allocated. If the root end time is at most the current start time, reuse that room by polling it. Otherwise allocate a new room by pushing another end time.

Common mistakes

×Sorting by end time instead of start time, which loses the chronological order of room requests.
×Using a max-heap, which hides the room that becomes free first.
×Checking only strict inequality and failing to reuse a room when one meeting ends exactly when another starts.
×Forgetting that the answer is the maximum number of allocated rooms, not the length of the input.

Algorithm Explanation

Key idea

Sort meetings by start time. Store the end time of each allocated room in a min-heap. The root is the room that becomes available first. For the next meeting, if the root end time is less than or equal to the meeting start, poll it and reuse that room. Then push the current meeting end time. The largest heap size seen is the number of rooms required.

Heap walkthrough

Use intervals = [[0,30],[5,10],[15,20]]. After sorting, the order is unchanged. Meeting [0,30] starts first, so push end 30 and the heap is [30]. Meeting [5,10] starts while 30 is still busy, so allocate another room and push 10; the heap is shown as [10,30]. Meeting [15,20] sees root 10, which is free before 15. Poll 10, push 20, and the heap becomes [20,30]. The largest heap size was 2, so two rooms are required.

Algorithm

Sort intervals by start time.
Create a min-heap of meeting end times.
For each meeting in sorted order, compare its start time with the smallest end time in the heap.
If the smallest end time is less than or equal to the current start, poll it because that room can be reused.
Push the current meeting end time into the heap.
Track the maximum heap size seen during the scan.
Return that maximum as the room count.

Solutions

Solution: Min-heap of room end times

When to prefer this:

Use this as the standard interview solution when intervals arrive as an array and can be sorted first.

Sort meetings by start time, then maintain a min-heap of room end times. The heap root is the only room that matters for reuse: if it has not ended yet, no allocated room has ended.

Step-by-step

Return 0 for an empty input if the platform allows it.
Sort all intervals by their start time.
Create a min-heap ordered by end time.
For each interval, poll the root when it is less than or equal to the current start.
Push the current end time because the meeting now occupies a room.
Update the answer with the heap size after the push.

Time

O(n log n)

Space

O(n)

Sorting dominates the scan; the heap can hold one end time for every allocated room in the worst case.

Java implementation

Loading…

Dry Run

Sample input

intervals = [[0,30],[5,10],[15,20]]. Heap values are room end times, shown in sorted order for readability.

meeting	earliest end before	action	heap after	rooms needed
[0,30]	none	allocate first room	[30]	1
[5,10]	30	30 is after 5, allocate another room	[10,30]	2
[15,20]	10	10 is before 15, reuse that room	[20,30]	2

The heap reaches size 2 and never needs a third room. The root comparison captures the only room that could possibly be reused first.

Interview Tips

Say the heap stores end times, not intervals. That immediately explains the comparator and the reuse check. Be explicit that end <= start means the room is free. A common follow-up asks for Meeting Rooms I; that problem only asks whether any overlap exists, so sorting and comparing adjacent intervals is enough.

Likely follow-ups

How would you solve the easier Meeting Rooms problem that only asks if one person can attend all meetings?
How would the answer change if intervals were streamed online and could not be sorted first?
Can you solve this with two sorted arrays of starts and ends instead of a heap?
How would you return the actual room assignment for each meeting?

Key Takeaways

Sort by start time so meetings are considered in the order rooms are requested.
A min-heap of end times exposes the room that frees first.
If the earliest room is still busy, all allocated rooms are busy.
The maximum heap size is the minimum number of rooms needed.

Reusable template: Greedy resource scheduling: sort events by start time, keep resource release times in a min-heap, and reuse the earliest-free resource whenever possible.