Meeting Rooms II

Description

You are given an array of meeting time intervals where each interval consists of a start time and an end time, represented as intervals[i] = [start_i, end_i] (with start_i < end_i).

Your task is to determine the minimum number of conference rooms needed so that all meetings can take place without any scheduling conflicts. Two meetings conflict if their time ranges overlap. However, a meeting that ends at time t does not conflict with a meeting that starts at time t — the room is considered free at the exact moment a meeting ends.

For example, if one meeting occupies a room from time 0 to 30, and another meeting runs from time 5 to 10, both meetings overlap in the window [5, 10), so they cannot share the same room. A second room is required.

Examples

Example 1

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

Output: 2

Explanation: The first meeting runs from time 0 to 30 and occupies Room 1 throughout. The second meeting [5, 10] starts while Room 1 is busy, so it needs Room 2. The third meeting [15, 20] also overlaps with Room 1, but Room 2 is free after time 10, so the third meeting reuses Room 2. The maximum number of rooms in use at any moment is 2.

Example 2

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

Output: 1

Explanation: Meeting [2, 4] ends at time 4, and meeting [7, 10] starts at time 7. Since 4 < 7, these two meetings do not overlap at all. One conference room is sufficient for both.

Example 3

Input: intervals = [[1, 5], [2, 6], [3, 7], [4, 8]]

Output: 4

Explanation: At time 4, all four meetings are in progress simultaneously: [1,5], [2,6], [3,7], and [4,8] all contain time 4 in their active range. Therefore, we need 4 separate rooms — one for each meeting.

Constraints

0 ≤ intervals.length ≤ 500
0 ≤ intervals[i][0] < intervals[i][1] ≤ 1,000,000
Each interval represents a valid meeting with start < end
A meeting ending at time t does not conflict with a meeting starting at time t

Editorial

Brute Force

Intuition

The simplest way to think about this problem is to simulate the room assignment process directly, much like a receptionist would in real life.

Imagine you are a conference room manager. You have a list of meeting requests. You process them one by one. For each new meeting, you check every room that is currently occupied. If any room's current meeting ends before (or exactly when) the new meeting starts, you can reuse that room. If no room is available, you open a new one.

To make the simulation predictable, we first sort all meetings by their start time so we process them in chronological order. Then, for each meeting, we scan through all currently assigned rooms to see if any room is free. A room is free if the meeting currently assigned to it has already ended (i.e., its end time is ≤ the new meeting's start time).

If we find a free room, we reassign it to the new meeting. If no room is free, we allocate a new room. The total number of rooms allocated at the end is our answer.

This works correctly but is slow because for each of the n meetings, we might scan through up to n rooms — leading to O(n²) time.

Step-by-Step Explanation

Let's trace through with intervals = [[0, 30], [5, 10], [15, 20]]:

Step 1: Sort intervals by start time → [[0, 30], [5, 10], [15, 20]] (already sorted).

Step 2: Process meeting [0, 30]. No rooms exist yet. Allocate Room 1. Rooms: [end=30].

Step 3: Process meeting [5, 10]. Check Room 1: its end time is 30, and 30 > 5, so Room 1 is still busy. No free room found. Allocate Room 2. Rooms: [end=30, end=10].

Step 4: Process meeting [15, 20]. Check Room 1: end=30, and 30 > 15, so Room 1 is busy. Check Room 2: end=10, and 10 ≤ 15, so Room 2 is free! Reassign Room 2 to this meeting. Rooms: [end=30, end=20].

Step 5: All meetings processed. Total rooms used = 2.

Result: 2

Brute Force — Simulating Room Assignment — Watch how we process each meeting in start-time order, scanning through existing rooms to find a free one or allocating a new room when none is available.

Algorithm

Sort all intervals by their start time.
Maintain a list rooms that stores the end time of the meeting currently assigned to each room.
For each meeting in sorted order:
- Scan through rooms to find any room whose end time ≤ current meeting's start time.
- If found, update that room's end time to the current meeting's end time (reuse the room).
- If not found, append the current meeting's end time to rooms (allocate a new room).
Return the length of rooms.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        
        // Sort by start time
        sort(intervals.begin(), intervals.end());
        
        // rooms[i] stores the end time of the meeting in room i
        vector<int> rooms;
        
        for (auto& interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            bool found = false;
            
            // Try to find a free room
            for (int i = 0; i < rooms.size(); i++) {
                if (rooms[i] <= start) {
                    rooms[i] = end; // Reuse room
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                rooms.push_back(end); // Allocate new room
            }
        }
        
        return rooms.size();
    }
};

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        
        # Sort by start time
        intervals.sort(key=lambda x: x[0])
        
        # rooms[i] stores the end time of the meeting in room i
        rooms = []
        
        for start, end in intervals:
            # Try to find a free room
            found = False
            for i in range(len(rooms)):
                if rooms[i] <= start:
                    rooms[i] = end  # Reuse room
                    found = True
                    break
            
            if not found:
                rooms.append(end)  # Allocate new room
        
        return len(rooms)

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        
        // Sort by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // rooms stores the end time of each room's current meeting
        List<Integer> rooms = new ArrayList<>();
        
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            boolean found = false;
            
            // Try to find a free room
            for (int i = 0; i < rooms.size(); i++) {
                if (rooms.get(i) <= start) {
                    rooms.set(i, end); // Reuse room
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                rooms.add(end); // Allocate new room
            }
        }
        
        return rooms.size();
    }
}

Complexity Analysis

Time Complexity: O(n²)

Sorting takes O(n log n). For each of the n meetings, we scan through up to n rooms to check availability. In the worst case (all meetings overlap), every meeting opens a new room, and we scan all existing rooms before deciding. This gives O(n) work per meeting × n meetings = O(n²). The sorting cost is dominated, so total is O(n²).

Space Complexity: O(n)

The rooms list can grow up to size n if every meeting requires its own room (all overlap). No other data structure grows with input size.

Why This Approach Is Not Efficient

The brute force scans all existing rooms for each new meeting. With up to 500 meetings, that's potentially 500 × 500 = 250,000 operations — manageable for this constraint, but the approach doesn't scale.

The core inefficiency is in how we search for a free room. We linearly scan through all rooms every time, but we only care about whether the earliest-ending room has finished. If the room that frees up soonest is still busy, then all other rooms are certainly busy too.

This insight suggests we should maintain the rooms sorted by their end times, so we can check the earliest-ending room in O(1) time instead of O(n). A min heap (priority queue) gives us exactly this capability — O(1) to peek at the minimum, O(log n) to insert or remove.

Better Approach - Min Heap

Intuition

Instead of scanning all rooms linearly to find a free one, we can use a min heap (priority queue) that always keeps the earliest-ending meeting on top.

Think of it like a digital display board showing all conference rooms sorted by when they become available. When a new meeting request comes in, you just look at the top of the board — the room that frees up earliest. If that room will be free before the new meeting starts, you reassign it. If even the earliest room is still busy, then all rooms are busy and you need a new one.

The min heap stores the end times of all currently active meetings. For each new meeting (processed in start-time order):

Peek at the heap's top (the smallest end time). If this end time ≤ the new meeting's start, that room is free — pop it and reuse.
Push the new meeting's end time onto the heap (whether reusing or allocating a new room).

The maximum size the heap ever reaches is the answer — that is the peak number of simultaneous meetings.

Step-by-Step Explanation

Let's trace through with intervals = [[0, 30], [5, 10], [15, 20]]:

Step 1: Sort by start time → [[0, 30], [5, 10], [15, 20]] (already sorted).

Step 2: Initialize an empty min heap.

Step 3: Process meeting [0, 30]. Heap is empty, so no room to reuse. Push end time 30 onto heap. Heap: [30]. Rooms needed: 1.

Step 4: Process meeting [5, 10]. Peek at heap top: 30. Is 30 ≤ 5? No — the earliest-ending room is still busy until time 30. We need a new room. Push 10. Heap: [10, 30]. Rooms needed: 2.

Step 5: Process meeting [15, 20]. Peek at heap top: 10. Is 10 ≤ 15? Yes — that room's meeting ended at time 10, which is before time 15. Pop 10 (reuse the room). Push 20. Heap: [20, 30]. Rooms needed: still 2.

Step 6: All meetings processed. Maximum heap size reached was 2.

Result: 2

Min Heap — Tracking Earliest Room Availability — Watch how the min heap always surfaces the earliest-ending meeting, letting us decide in O(1) whether a room can be reused or a new one is needed.

Algorithm

Sort all intervals by their start time.
Initialize an empty min heap.
For each meeting in sorted order:
- If the heap is not empty and heap_top ≤ current_start, pop the top (reuse that room).
- Push the current meeting's end time onto the heap.
Return the size of the heap (this equals the maximum number of rooms needed).

Code

#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        
        // Sort by start time
        sort(intervals.begin(), intervals.end());
        
        // Min heap stores end times of active meetings
        priority_queue<int, vector<int>, greater<int>> minHeap;
        
        for (auto& interval : intervals) {
            // If earliest-ending room is free, reuse it
            if (!minHeap.empty() && minHeap.top() <= interval[0]) {
                minHeap.pop();
            }
            // Assign this meeting to a room
            minHeap.push(interval[1]);
        }
        
        return minHeap.size();
    }
};

import heapq

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        
        # Sort by start time
        intervals.sort(key=lambda x: x[0])
        
        # Min heap stores end times of active meetings
        min_heap = []
        
        for start, end in intervals:
            # If earliest-ending room is free, reuse it
            if min_heap and min_heap[0] <= start:
                heapq.heappop(min_heap)
            # Assign this meeting to a room
            heapq.heappush(min_heap, end)
        
        return len(min_heap)

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        
        // Sort by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        
        // Min heap stores end times of active meetings
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        
        for (int[] interval : intervals) {
            // If earliest-ending room is free, reuse it
            if (!minHeap.isEmpty() && minHeap.peek() <= interval[0]) {
                minHeap.poll();
            }
            // Assign this meeting to a room
            minHeap.offer(interval[1]);
        }
        
        return minHeap.size();
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Sorting the intervals takes O(n log n). Then we iterate through n meetings, and each heap push/pop operation takes O(log n). Total: O(n log n) for sorting + O(n log n) for heap operations = O(n log n).

Space Complexity: O(n)

In the worst case (all meetings overlap), the min heap stores all n end times simultaneously. So the heap uses O(n) space.

Why This Approach Is Not Efficient

The min heap approach is already O(n log n), which is efficient. However, it can be argued that the heap operations (push and pop, each O(log n)) add overhead that isn't strictly necessary. The heap maintains the full set of room end times, but we only really need to know the total count of overlapping meetings at each moment.

The key insight for further optimization is: we don't need to track which room each meeting belongs to. We only need to know how many meetings are happening simultaneously at the peak moment. This leads us to a fundamentally different approach — instead of simulating room allocation, we can separate all start times and end times into two independent sorted arrays and sweep through them with two pointers. This avoids heap operations entirely, replacing O(log n) per step with O(1) per step (after the initial sort).

Optimal Approach - Sorted Events with Two Pointers

Intuition

Forget about rooms entirely. Instead, think about the problem as a timeline of events.

Every meeting creates two events: a start event (we need one more room) and an end event (we free one room). If we process all events in chronological order, the running count of active meetings at any point tells us how many rooms are in use. The peak of this running count is our answer.

Here is the elegant trick: separate all start times into one sorted list and all end times into another sorted list. Then use two pointers — one walking through starts, one walking through ends.

If the next start time comes before the next end time, a new meeting begins before any current one finishes → we need one more room. Advance the start pointer.
If the next end time comes first (or they are equal), a meeting ends → one room is freed. Advance the end pointer.

The maximum value of the running room count during this sweep is the minimum number of rooms needed.

Why does this work even though we separated starts and ends from their original pairings? Because we only care about how many meetings overlap, not which ones overlap. At any given time, the count of meetings that have started but not yet ended is the number of rooms in use — and the two-pointer sweep computes exactly this.

Step-by-Step Explanation

Let's trace through with intervals = [[0, 30], [5, 10], [15, 20]]:

Step 1: Extract start times: [0, 5, 15]. Extract end times: [10, 20, 30]. Sort both.

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

Step 2: Initialize pointers s=0, e=0, count=0, max_rooms=0.

Step 3: Compare starts[0]=0 vs ends[0]=10. Since 0 < 10, a meeting starts before any ends. Increment count to 1. Advance s to 1. max_rooms = max(0, 1) = 1.

Step 4: Compare starts[1]=5 vs ends[0]=10. Since 5 < 10, another meeting starts before the first end. Increment count to 2. Advance s to 2. max_rooms = max(1, 2) = 2.

Step 5: Compare starts[2]=15 vs ends[0]=10. Since 15 ≥ 10, a meeting ends before (or at) the next start. Decrement count to 1. Advance e to 1.

Step 6: Compare starts[2]=15 vs ends[1]=20. Since 15 < 20, a meeting starts. Increment count to 2. Advance s to 3. max_rooms = max(2, 2) = 2.

Step 7: s=3 has gone past all start times. We're done. The sweep is complete.

Result: max_rooms = 2

Two Pointers — Sweeping Through Sorted Start and End Times — Watch how two pointers independently traverse sorted start and end arrays. When a start comes first, we need a room; when an end comes first, we free one.

Algorithm

Extract all start times into one array and all end times into another array.
Sort both arrays independently.
Initialize two pointers s = 0 and e = 0, a counter count = 0, and max_rooms = 0.
While s < n (there are still start events to process):
- If starts[s] < ends[e]: a meeting starts before the next one ends → increment count, advance s.
- Else: a meeting ends before or at the next start → decrement count, advance e.
- Update max_rooms = max(max_rooms, count).
Return max_rooms.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) return 0;
        
        int n = intervals.size();
        vector<int> starts(n), ends(n);
        
        for (int i = 0; i < n; i++) {
            starts[i] = intervals[i][0];
            ends[i] = intervals[i][1];
        }
        
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());
        
        int s = 0, e = 0;
        int count = 0, maxRooms = 0;
        
        while (s < n) {
            if (starts[s] < ends[e]) {
                count++;
                s++;
            } else {
                count--;
                e++;
            }
            maxRooms = max(maxRooms, count);
        }
        
        return maxRooms;
    }
};

class Solution:
    def minMeetingRooms(self, intervals: list[list[int]]) -> int:
        if not intervals:
            return 0
        
        starts = sorted(iv[0] for iv in intervals)
        ends = sorted(iv[1] for iv in intervals)
        
        s = e = 0
        count = max_rooms = 0
        n = len(intervals)
        
        while s < n:
            if starts[s] < ends[e]:
                count += 1
                s += 1
            else:
                count -= 1
                e += 1
            max_rooms = max(max_rooms, count)
        
        return max_rooms

import java.util.*;

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        
        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];
        }
        
        Arrays.sort(starts);
        Arrays.sort(ends);
        
        int s = 0, e = 0;
        int count = 0, maxRooms = 0;
        
        while (s < n) {
            if (starts[s] < ends[e]) {
                count++;
                s++;
            } else {
                count--;
                e++;
            }
            maxRooms = Math.max(maxRooms, count);
        }
        
        return maxRooms;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

We sort both the starts and ends arrays, each of size n. Sorting dominates at O(n log n). The two-pointer sweep itself is O(n) — each pointer advances at most n times, and each step is O(1). Total: O(n log n).

Space Complexity: O(n)

We create two auxiliary arrays of size n (starts and ends). This is O(n) extra space. Note: we cannot avoid O(n log n) time because the problem inherently requires comparing events in sorted order, and comparison-based sorting has an Ω(n log n) lower bound. This approach achieves the theoretical optimum.