Meeting Rooms II

Difficulty: Medium Source: NeetCode

Problem

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of conference rooms required.

Example 1: Input: intervals = [[0,30],[5,10],[15,20]] Output: 2

Example 2: Input: intervals = [[7,10],[2,4]] Output: 1

Constraints:

• 1 <= intervals.length <= 10^4
• 0 <= start_i < end_i <= 10^6

Prerequisites

Before attempting this problem, you should be comfortable with:

• Sorting — sorting meetings by start time to process them in order
• Min-heap (priority queue) — quickly finding the room that frees up soonest
• Two pointers — the alternative approach using sorted start and end arrays

1. Brute Force

Intuition

Simulate the process directly: for each meeting, scan all existing rooms to find one that has already finished. If none is free, open a new room. This is correct but slow because the “find a free room” scan is linear.

Algorithm

1. Sort intervals by start time.
2. Maintain a list rooms where each entry is the end time of the meeting currently occupying that room.
3. For each meeting [start, end]:
   • Find any room whose current meeting ends by start. If found, update that room’s end time to end.
   • Otherwise add a new room with end time end.
4. Return len(rooms).

Solution

def min_meeting_rooms_brute(intervals):
    intervals.sort(key=lambda x: x[0])
    rooms = []  # each entry = end time of meeting in that room

    for start, end in intervals:
        # Try to find a free room
        assigned = False
        for i in range(len(rooms)):
            if rooms[i] <= start:
                rooms[i] = end
                assigned = True
                break
        if not assigned:
            rooms.append(end)

    return len(rooms)


print(min_meeting_rooms_brute([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms_brute([[7,10],[2,4]]))           # 1
print(min_meeting_rooms_brute([[1,5],[2,6],[3,7]]))      # 3

Complexity

• Time: O(n²) — for each meeting, we scan all rooms
• Space: O(n) — rooms list

2. Min-Heap of End Times

Intuition

Sort meetings by start time. Maintain a min-heap that holds the end times of all currently occupied rooms — so the top of the heap is the room that frees up soonest. When the next meeting starts, peek at the heap: if the earliest-ending room is already free (its end time ≤ current meeting’s start), pop it and reuse it; otherwise push a new room. The heap size at the end equals the number of rooms needed.

Algorithm

1. Sort intervals by start time.
2. Initialize a min-heap heap.
3. For each meeting [start, end]:
   • If heap is non-empty and heap[0] <= start, pop the earliest-ending room (it is free).
   • Push end onto the heap (allocate or reuse a room).
4. Return len(heap).

Solution

import heapq

def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []  # min-heap of end times

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)  # reuse the earliest-freed room
        heapq.heappush(heap, end)

    return len(heap)


print(min_meeting_rooms([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms([[7,10],[2,4]]))           # 1
print(min_meeting_rooms([[1,5],[2,6],[3,7]]))      # 3
print(min_meeting_rooms([[1,10]]))                 # 1

Complexity

• Time: O(n log n) — sorting + heap operations (each push/pop is O(log n))
• Space: O(n) — heap can hold all n meetings in the worst case

3. Two Pointers on Sorted Start and End Arrays

Intuition

Separate the start times and end times into two sorted arrays. Use two pointers s and e. Process events in chronological order: if the next event is a start, we need a new room (increment rooms); if the next event is an end, a room is freed (decrement rooms, advance e). Track the maximum rooms used at any point.

Algorithm

1. Create starts = sorted([i[0] for i in intervals]) and ends = sorted([i[1] for i in intervals]).
2. Initialize rooms = 0, max_rooms = 0, s = 0, e = 0.
3. While s < n:
   • If starts[s] < ends[e]: a meeting starts before the earliest end — new room needed. Increment rooms, advance s.
   • Else: a meeting ends before or when this one starts — free a room. Decrement rooms, advance e.
   • Update max_rooms = max(max_rooms, rooms).
4. Return max_rooms.

Solution

def min_meeting_rooms_two_pointers(intervals):
    n = len(intervals)
    starts = sorted(i[0] for i in intervals)
    ends = sorted(i[1] for i in intervals)

    rooms = 0
    max_rooms = 0
    e = 0

    for s in range(n):
        if starts[s] < ends[e]:
            rooms += 1
        else:
            rooms -= 1
            e += 1
        max_rooms = max(max_rooms, rooms)

    return max_rooms


print(min_meeting_rooms_two_pointers([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms_two_pointers([[7,10],[2,4]]))           # 1
print(min_meeting_rooms_two_pointers([[1,5],[2,6],[3,7]]))      # 3

Complexity

• Time: O(n log n) — two sorts
• Space: O(n) — two extra arrays

Common Pitfalls

Using < vs <= when checking if a room is free. If a meeting ends at time 5 and another starts at time 5, the room IS free. Use heap[0] <= start (not <) to allow back-to-back meetings in the same room.

Forgetting to sort before using the heap. The heap approach only works correctly when meetings are processed in start-time order. Sorting first is mandatory.

Confusing rooms opened vs maximum simultaneous rooms. The question asks for the peak concurrent rooms. The heap size at the end gives you this naturally — it counts rooms that were never freed.