Meeting Rooms II

medium
IntervalsArrayIntervalHeap / Priority QueueSorting

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], find the minimum number of conference rooms required so that all meetings can take place without conflicts.

A conference room can only host one meeting at a time. A room becomes available the moment a meeting ends, so a meeting ending at time t and a meeting starting at time t can use the same room.

Examples

Example 1

  • Input: intervals = [[0,30],[5,10],[15,20]]
  • Output: 2
  • Explanation: Meeting [0,30] occupies one room for the entire time. Meetings [5,10] and [15,20] can share a second room since they do not overlap. Two rooms are needed in total.

Example 2

  • Input: intervals = [[7,10],[2,4]]
  • Output: 1
  • Explanation: The meetings do not overlap, so a single room is sufficient.

Example 3

  • Input: intervals = [[0,5],[5,10],[0,10]]
  • Output: 2
  • Explanation: At time 0, meetings [0,5] and [0,10] both start simultaneously, requiring two rooms. Meeting [5,10] can reuse the room freed by [0,5].

Constraints

  • 1 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i < end_i <= 10^6

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Min-Heap (Priority Queue)

Intuition

We can simulate room allocation using a min-heap that tracks the end times of ongoing meetings. Sort the meetings by start time, then process each meeting in order. For each meeting, check if the earliest-ending meeting (heap top) has already finished. If so, that room can be reused -- pop it from the heap. Then push the current meeting's end time onto the heap. The heap size at any point represents the number of rooms in use. The maximum heap size during the process is the answer.

Algorithm

  1. Sort the intervals by start time.
  2. Initialize a min-heap. Push the end time of the first meeting.
  3. For each subsequent meeting:
  4. The size of the heap at the end is the minimum number of rooms required.
TimeO(n log n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        priority_queue<int, vector<int>, greater<int>> minHeap;

        for (auto& interval : intervals) {
            if (!minHeap.empty() && minHeap.top() <= interval[0]) {
                minHeap.pop();
            }
            minHeap.push(interval[1]);
        }

        return minHeap.size();
    }
};
Java 21
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        for (int[] interval : intervals) {
            if (!minHeap.isEmpty() && minHeap.peek() <= interval[0]) {
                minHeap.poll();
            }
            minHeap.offer(interval[1]);
        }

        return minHeap.size();
    }
}
Python 3.12
import heapq

def minMeetingRooms(intervals: List[List[int]]) -> int:
    intervals.sort()
    heap = []

    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        heapq.heappush(heap, end)

    return len(heap)
Go 1.26
import (
    "container/heap"
    "sort"
)

type IntHeap []int

func (h IntHeap) Len() int            { return len(h) }
func (h IntHeap) Less(i, j int) bool   { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int)        { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{})  { *h = append(*h, x.(int)) }
func (h *IntHeap) Pop() interface{} {
    old := *h
    n := len(old)
    val := old[n-1]
    *h = old[:n-1]
    return val
}

func minMeetingRooms(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    h := &IntHeap{}
    heap.Init(h)

    for _, interval := range intervals {
        if h.Len() > 0 && (*h)[0] <= interval[0] {
            heap.Pop(h)
        }
        heap.Push(h, interval[1])
    }

    return h.Len()
}
Approach 2

Chronological Ordering (Sweep Line)

Intuition

This approach separates start times and end times into two sorted arrays and processes them in chronological order using two pointers. Think of it as a timeline: every start event adds a room, every end event frees a room. By sorting both arrays and sweeping through start events, we check if a room has become free (end time <= current start time) before allocating a new one. The maximum number of rooms active at any point is the answer. This approach is elegant because it decouples the events and avoids the overhead of a heap.

Algorithm

  1. Extract all start times into one array and all end times into another. Sort both arrays.
  2. Use two pointers: `s` for start times and `e` for end times. Initialize `rooms` and `maxRooms` to 0.
  3. Iterate through start times. For each start time:
  4. Return `maxRooms`.
TimeO(n log n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        vector<int> starts, ends;
        for (auto& interval : intervals) {
            starts.push_back(interval[0]);
            ends.push_back(interval[1]);
        }
        sort(starts.begin(), starts.end());
        sort(ends.begin(), ends.end());

        int rooms = 0, maxRooms = 0;
        int s = 0, e = 0;
        int n = intervals.size();

        while (s < n) {
            if (starts[s] >= ends[e]) {
                rooms--;
                e++;
            }
            rooms++;
            s++;
            maxRooms = max(maxRooms, rooms);
        }

        return maxRooms;
    }
};
Java 21
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];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);

        int rooms = 0, maxRooms = 0;
        int s = 0, e = 0;

        while (s < n) {
            if (starts[s] >= ends[e]) {
                rooms--;
                e++;
            }
            rooms++;
            s++;
            maxRooms = Math.max(maxRooms, rooms);
        }

        return maxRooms;
    }
}
Python 3.12
def minMeetingRooms(intervals: List[List[int]]) -> int:
    starts = sorted(iv[0] for iv in intervals)
    ends = sorted(iv[1] for iv in intervals)

    rooms = 0
    max_rooms = 0
    s, e = 0, 0
    n = len(intervals)

    while s < n:
        if starts[s] >= ends[e]:
            rooms -= 1
            e += 1
        rooms += 1
        s += 1
        max_rooms = max(max_rooms, rooms)

    return max_rooms
Go 1.26
import "sort"

func minMeetingRooms(intervals [][]int) int {
    n := len(intervals)
    starts := make([]int, n)
    ends := make([]int, n)

    for i, iv := range intervals {
        starts[i] = iv[0]
        ends[i] = iv[1]
    }
    sort.Ints(starts)
    sort.Ints(ends)

    rooms, maxRooms := 0, 0
    s, e := 0, 0

    for s < n {
        if starts[s] >= ends[e] {
            rooms--
            e++
        }
        rooms++
        s++
        if rooms > maxRooms {
            maxRooms = rooms
        }
    }

    return maxRooms
}

Frequently asked questions

What is the optimal time complexity of Meeting Rooms II?

The most efficient approach in this guide ("Chronological Ordering (Sweep Line)") runs in O(n log n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Meeting Rooms II use?

Meeting Rooms II is a medium-level Intervals problem involving Array, Interval, Heap / Priority Queue. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Meeting Rooms II be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(n), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Loading editor...
Input
intervals=
[[0,30],[5,10],[15,20]]
Expected Output
2