Course4all
Join us on telegram
Home/dsa/Greedy/Meeting Rooms II

Meeting Rooms II

Master this topic with zero to advance depth.

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.

Visual Representation

Intervals: [[0, 30], [5, 10], [15, 20]] Room 1: [0--------------------------30] Room 2: [5---10] [15---20] Max overlapping at any time: 2 Result: 2
Medium

Examples

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

We need two rooms; one for [0, 30] and another for [5, 10] and [15, 20] sequentially.

Approach 1

Level I: Brute Force (Iterate All Time Points)

Intuition

Count the number of overlapping meetings at every possible time point. The maximum count across all time points is the minimum number of rooms needed.

Thought Process

  1. Find the minStart and maxEnd across all intervals.
  2. For every time tt from minStart to maxEnd:
    • Count how many meetings are active at time tt (i.e., start <= t < end).
  3. Return the maximum count found.
⏱ O(N * T) where T is the time range.💾 O(1)

Detailed Dry Run

[[0, 30], [5, 10], [15, 20]]

  • t=0: active=[[0,30]]. Count=1.
  • t=5: active=[[0,30], [5,10]]. Count=2.
  • t=15: active=[[0,30], [15,20]]. Count=2. Max count = 2.
java
public class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int[] i : intervals) {
            min = Math.min(min, i[0]);
            max = Math.max(max, i[1]);
        }
        int maxRooms = 0;
        for (int t = min; t < max; t++) {
            int count = 0;
            for (int[] i : intervals) {
                if (t >= i[0] && t < i[1]) count++;
            }
            maxRooms = Math.max(maxRooms, count);
        }
        return maxRooms;
    }
}
Approach 2

Level II: Chronological Sorting (Sweep Line)

Intuition

When a meeting starts, we need a room; when it ends, we free a room. If we process all start and end points in chronological order, the max number of overlapping meetings at any point is our answer.

Thought Process

  1. Separate starts and ends into two sorted arrays.
  2. Use two pointers to iterate through them.
  3. If startTime < endTime, a new meeting starts before an old one ends: increment rooms and startPtr.
  4. Else, a meeting ends: decrement rooms and endPtr.

Pattern: Sweep Line / Two Pointers

⏱ O(N log N)💾 O(N)

Detailed Dry Run

Starts: [0, 5, 15], Ends: [10, 20, 30]

  1. t=0: Start [0,30]. rooms=1. max=1.
  2. t=5: Start [5,10]. rooms=2. max=2.
  3. t=10: End [5,10]. rooms=1.
  4. t=15: Start [15,20]. rooms=2. max=2.
java
public class Solution {
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] starts = new int[n], 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, max = 0, s = 0, e = 0;
        while (s < n) {
            if (starts[s] < ends[e]) {
                rooms++; s++;
            } else {
                rooms--; e++;
            }
            max = Math.max(max, rooms);
        }
        return max;
    }
}
Approach 3

Level III: Optimal Greedy (Min-Heap)

Intuition

As we process meetings by start time, we use a Min-Heap to track the end times of rooms currently in use. The top of the heap is the room that will be free soonest.

Thought Process

  1. Sort meetings by start time.
  2. Add the first meeting's end time to a Min-Heap.
  3. For each next meeting, if its start >= heap.peek() (earliest end), we can reuse that room: heap.pop().
  4. Always push current meeting's end time to the heap.
  5. Answer is heap.size().

Pattern: Resource Allocation / Priority Queue

⏱ O(N log N) for sorting and heap ops.💾 O(N) for heap.

Detailed Dry Run

[[0,30],[5,10],[15,20]] Sorted

  1. [0,30]: Heap=[30], rooms=1
  2. [5,10]: 5 < 30? YES. Heap=[10, 30], rooms=2
  3. [15,20]: 15 >= 10? YES. Pop 10, Push 20. Heap=[20, 30], rooms=2
java
import java.util.*;
public class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.add(intervals[0][1]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= pq.peek()) pq.poll();
            pq.add(intervals[i][1]);
        }
        return pq.size();
    }
}
← Previous QuestionMaximum Length of Pair Chain
Next Question →Candy Distribution