Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/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] = [starti, endi], return the minimum number of conference rooms required.

Visual Representation

intervals = [[0,30],[5,10],[15,20]] Timeline: 0 5 10 15 20 30 |--|---|---|----|----| [0 30] (Room 1) [5 10] (Room 2) [15 20] (Room 2 - reused) Max overlapping at any time: 2
Medium

Examples

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Input: intervals = [[7,10],[2,4]]
Output: 1
Approach 1

Level I: Min-Heap (Interval Management)

Intuition

Sort the meetings by start time. Use a Min-Heap to track the end times of meetings currently in progress. If a new meeting starts after the earliest meeting ends (root of the heap), we can reuse that room.

Thought Process

  1. Sort intervals by start time.
  2. Initialize a Min-Heap to store end times.
  3. For each interval:
    • If heap is not empty and heap.peek() <= current.start, pop the heap (room becomes free).
    • Push current interval's end time to heap.
  4. The final size of the heap is the number of rooms needed.
⏱ O(N log N)💾 O(N)

Detailed Dry Run

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

  1. Sorted: [[0,30],[5,10],[15,20]]
  2. Int [0,30]: Heap [30]
  3. Int [5,10]: Heap.peek(30) > 5. Push 10. Heap [10, 30]
  4. Int [15,20]: Heap.peek(10) <= 15. Pop 10. Push 20. Heap [20, 30] Result: Heap size = 2
java
import java.util.*;
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if (intervals.length == 0) return 0;
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int[] interval : intervals) {
            if (!pq.isEmpty() && pq.peek() <= interval[0]) pq.poll();
            pq.add(interval[1]);
        }
        return pq.size();
    }
}
Approach 2

Level II: Sweep Line (Difference Array Logic)

Intuition

Record all 'start' and 'end' events. A 'start' event increases the room count by 1, and an 'end' event decreases it by 1. The maximum room count at any point is our answer.

Thought Process

  1. For each interval [s,e][s, e], create two points: (s,+1)(s, +1) and (e,−1)(e, -1).
  2. Sort todos points by time.
  3. If times are equal, process end events (−1)(-1) before start events (+1)(+1) if the interval is exclusive, OR start before end if inclusive. (LeetCode meetings are inclusive of start, exclusive of end, so end before start at same time).
  4. Traverse through sorted points and maintain a running sum.
⏱ O(N log N)💾 O(N)

Detailed Dry Run

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

  1. Events: (0,+1), (30,-1), (5,+1), (10,-1), (15,+1), (20,-1)
  2. Sorted: (0,+1), (5,+1), (10,-1), (15,+1), (20,-1), (30,-1)
  3. Sums: 1 -> 2 -> 1 -> 2 -> 1 -> 0 Max Sum: 2
java
import java.util.*;
class Solution {
    public int minMeetingRooms(int[][] intervals) {
        List<int[]> events = new ArrayList<>();
        for (int[] i : intervals) {
            events.add(new int[]{i[0], 1});
            events.add(new int[]{i[1], -1});
        }
        Collections.sort(events, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int rooms = 0, maxRooms = 0;
        for (int[] e : events) {
            rooms += e[1];
            maxRooms = Math.max(maxRooms, rooms);
        }
        return maxRooms;
    }
}
Approach 3

Level III: Two Pointers (Chronological Ordering)

Intuition

Separate start times and end times and sort both. Iterate through the start times. If a start time is before the earliest end time, we need a room. If not, a room just became free, so we can move the end-time pointer.

Logic Steps

  1. Extract all starts and ends into separate arrays.
  2. Sort both arrays.
  3. Use two pointers s and e.
  4. If starts[s] < ends[e], increment usedRooms and s.
  5. Else (room freed), increment e and s (total rooms stays same).
⏱ O(N log N)💾 O(N) for separate arrays

Detailed Dry Run

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

  1. s=0, e=0: starts[0]=0 < ends[0]=10 -> rooms=1, s=1
  2. s=1, e=0: starts[1]=5 < ends[0]=10 -> rooms=2, s=2
  3. s=2, e=0: starts[2]=15 >= ends[0]=10 -> rooms=2, e=1, s=3 Result: 2 rooms.
java
import java.util.Arrays;

public class Main {
    public static int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] start = new int[n];
        int[] end = new int[n];
        for (int i = 0; i < n; i++) {
            start[i] = intervals[i][0];
            end[i] = intervals[i][1];
        }
        Arrays.sort(start);
        Arrays.sort(end);
        
        int rooms = 0, e = 0;
        for (int s = 0; s < n; s++) {
            if (start[s] < end[e]) rooms++;
            else e++;
        }
        return rooms;
    }

    public static void main(String[] args) {
        System.out.println(minMeetingRooms(new int[][]{{0,30},{5,10},{15,20}})); // 2
    }
}
← Previous QuestionK Closest Points to Origin
Next Question →Rearrange String k Distance Apart