DSAPrep
MediumIntervals

Meeting Rooms II

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
Explanation: [0,30] and [5,10] overlap, and [0,30] and [15,20] overlap, so two rooms are needed; no point in time needs a third room.

Example 2

Input: intervals = [[7,10],[2,4]]
Output: 1
Explanation: [2,4] ends before [7,10] starts, so both meetings can share the same room.

Constraints

  • 1 <= intervals.length <= 10^4
  • 0 <= start_i < end_i <= 10^6
View original on LeetCode ↗

Brute Force (Count Overlaps at Every Start)

Time O(n²)Space O(1)

The number of rooms needed is the maximum number of meetings happening at the same time. For every meeting’s start time, count how many other meetings are in progress at that instant; the answer is the largest such count.

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        max_rooms = 0
        for s1, e1 in intervals:
            concurrent = 0
            for s2, e2 in intervals:
                if s2 <= s1 < e2:
                    concurrent += 1
            max_rooms = max(max_rooms, concurrent)
        return max_rooms

This checks every pair of meetings — O(n²) time — and misses the fact that sorting the start and end times lets us sweep through time in one pass.

Min-Heap of Room End Times

OptimalTime O(n log n)Space O(n)

Sort meetings by start time. Keep a min-heap holding the end time of every meeting currently occupying a room — the top of the heap is always the room that frees up soonest. For each meeting (in start order): if the earliest-freeing room’s end time is at or before this meeting’s start, that room is free, so pop it and reuse it; otherwise no room is free and a new one is pushed. Push the current meeting’s end time either way. The number of rooms in use at any point is the heap’s size, so the answer is the largest size the heap ever reaches.

import heapq


class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        intervals.sort(key=lambda iv: iv[0])
        heap = [intervals[0][1]]  # end times of occupied rooms
        for start, end in intervals[1:]:
            if heap[0] <= start:
                heapq.heappop(heap)  # earliest room just freed up, reuse it
            heapq.heappush(heap, end)
        return len(heap)

Tracing intervals = [[0,30],[5,10],[15,20]] (already sorted by start):

Sorted intervals

[0, 30]
[5, 10]
[15, 20]
1 / 3
merging

Process [0,30]: push its end time. Heap of room end-times: [30]. Rooms in use: 1.

The heap’s size peaked at 2, so 2 rooms are required.

Complexity: sorting costs O(n log n), and each of the n meetings does one heap push/pop (O(log n)) → O(n log n) time; the heap holds up to n end times → O(n) space.