Meeting Rooms II

Problem Description

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

Examples

Constraints

• 1 ≤ intervals.length ≤ 10⁴
• intervals[i].length == 2
• 0 ≤ start < end ≤ 10⁶

Tracking Peak Room Demand with Chronological Event Sorting

To find the minimum number of rooms, we need to know the maximum number of meetings occurring simultaneously at any point in time.

Instead of looking at intervals as pairs, we can split them into individual events:

• A meeting starts at time start (increases room count by 1).
• A meeting ends at time end (decreases room count by 1).

We extract all start times and end times, and sort both arrays independently. We then use two pointers to iterate through them chronologically:

• If start[startPointer] < end[endPointer], a new meeting is starting before the oldest meeting has finished. We increment our active room count and advance the startPointer.
• If start[startPointer] >= end[endPointer], a meeting has finished. We decrement our active room count and advance the endPointer.

We maintain a running maximum of the active room count, which represents the peak demand.

Solution 1: Chronological Event Sorting (Two Pointers)

Extract and sort start and end times, then scan them using two pointers to track active rooms.

import java.util.Arrays;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n];
        int[] ends = new int[n];

        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }

        // sort both arrays independently
        Arrays.sort(starts);
        Arrays.sort(ends);

        int startPtr = 0, endPtr = 0;
        int activeRooms = 0;
        int maxRooms = 0;

        while (startPtr < n) {
            if (starts[startPtr] < ends[endPtr]) {
                activeRooms++; // new meeting starts, increment count
                startPtr++;
            } else {
                activeRooms--; // meeting finishes, decrement count
                endPtr++;
            }
            maxRooms = Math.max(maxRooms, activeRooms);
        }

        return maxRooms;
    }
}

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        starts = sorted([i[0] for i in intervals])
        ends = sorted([i[1] for i in intervals])

        start_ptr = 0
        end_ptr = 0
        active_rooms = 0
        max_rooms = 0

        while start_ptr < len(intervals):
            if starts[start_ptr] < ends[end_ptr]:
                active_rooms += 1  # new meeting starts, increment count
                start_ptr += 1
            else:
                active_rooms -= 1  # meeting finishes, decrement count
                end_ptr += 1
            max_rooms = max(max_rooms, active_rooms)

        return max_rooms

#include <vector>
#include <algorithm>

class Solution {
public:
    int minMeetingRooms(std::vector<std::vector<int>>& intervals) {
        int n = intervals.size();
        std::vector<int> starts(n);
        std::vector<int> ends(n);

        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }

        // sort both arrays independently
        std::sort(starts.begin(), starts.end());
        std::sort(ends.begin(), ends.end());

        int startPtr = 0, endPtr = 0;
        int activeRooms = 0;
        int maxRooms = 0;

        while (startPtr < n) {
            if (starts[startPtr] < ends[endPtr]) {
                activeRooms++; // new meeting starts, increment count
                startPtr++;
            } else {
                activeRooms--; // meeting finishes, decrement count
                endPtr++;
            }
            maxRooms = std::max(maxRooms, activeRooms);
        }

        return maxRooms;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n) where n is the number of intervals. Sorting the start and end arrays dominates the complexity. The two-pointer traversal takes O(n) time.
• Space Complexity: O(n) to store the start and end coordinate lists.

Where it breaks: If the list of meetings is extremely large and we need to process them as a real-time stream rather than a static list, sorting everything upfront is impossible. In that case, using a min-heap to track active meeting end times (as explained in the alternative section) is better.

Solution 2: Min-Heap / Priority Queue

Sort the intervals by their start times. Maintain a min-heap containing the end times of active meetings. For each meeting, if its start time is greater than or equal to the minimum end time in the heap (meaning a room has become free), pop the oldest meeting. Push the current meeting’s end time. The size of the heap at the end is the minimum rooms required.

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;

        // sort by start times
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        // min-heap to store meeting end times
        PriorityQueue<Integer> allocator = new PriorityQueue<>();
        allocator.add(intervals[0][1]);

        for (int i = 1; i < intervals.length; i++) {
            // if a room has become free, reuse it by updating its end time
            if (intervals[i][0] >= allocator.peek()) {
                allocator.poll();
            }
            allocator.add(intervals[i][1]);
        }

        return allocator.size();
    }
}

import heapq


class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0

        # sort by start times
        intervals.sort(key=lambda x: x[0])

        # min-heap to store meeting end times
        allocator = []
        heapq.heappush(allocator, intervals[0][1])

        for i in range(1, len(intervals)):
            # if a room has become free, reuse it
            if intervals[i][0] >= allocator[0]:
                heapq.heappop(allocator)
            heapq.heappush(allocator, intervals[i][1])

        return len(allocator)

#include <vector>
#include <queue>
#include <algorithm>

class Solution {
public:
    int minMeetingRooms(std::vector<std::vector<int>>& intervals) {
        if (intervals.empty()) return 0;

        // sort by start times
        std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });

        // min-heap to store meeting end times
        std::priority_queue<int, std::vector<int>, std::greater<int>> allocator;
        allocator.push(intervals[0][1]);

        for (size_t i = 1; i < intervals.size(); i++) {
            // if a room has become free, reuse it
            if (intervals[i][0] >= allocator.top()) {
                allocator.pop();
            }
            allocator.push(intervals[i][1]);
        }

        return allocator.size();
    }
};

Complexity Analysis:

• Time Complexity: O(n log n). Sorting is O(n log n), and each of the n push/pop operations on the heap takes O(log n) time.
• Space Complexity: O(n) to store meeting end times in the heap in the worst case (all meetings overlap).

Where it breaks: Like Solution 1, this requires sorting the intervals array first. The heap approach uses O(n) memory in the worst case, but is ideal if meetings are processed dynamically in sorted start time order.

Common Mistakes

• Incorrect comparison when a meeting starts exactly when another ends. If a meeting ends at 10 and another starts at 10, they do not overlap. The check must be starts[startPtr] < ends[endPtr] (strict inequality). If you check <=, you will allocate an extra room unnecessarily.
• Sorting start and end times together as pairs. To use the two-pointer approach, you must sort the start and end coordinates independently. If you keep them paired, the pointer scan fails.
• Assuming the peak count is always the last active rooms value. You must maintain a maxRooms variable that records the maximum value of activeRooms reached during the scan.

Frequently Asked Questions

Why is it safe to sort starts and ends arrays independently? Because we only need to know how many meetings are active at any point. When we sort them independently, we lose track of which start time corresponds to which end time, but the chronological order of start and end events remains correct, which is sufficient to count active rooms.

Can this be solved using coordinate compression and prefix sums? Yes. You can use a map to store +1 at start times and -1 at end times, and then iterate through the sorted keys of the map to calculate prefix sums. This is useful when the number of intervals is small compared to coordinate values.

What does this problem test in interviews? It tests your ability to break range constraints into discrete events, manage multiple pointers chronologically, and apply min-heaps to resource scheduling.

← All Problems