Meeting Rooms II

Problem Statement

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

Examples

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation:
- Meeting [0,30] uses Room 1
- Meeting [5,10] needs Room 2 (overlaps with [0,30])
- Meeting [15,20] can use Room 2 (starts after [5,10] ends)

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1
Explanation: No overlaps, only 1 room needed

Example 3:

Input: intervals = [[1,5],[2,6],[3,7],[4,8]]
Output: 4
Explanation: All meetings overlap, need 4 separate rooms

Constraints

• 1 <= intervals.length <= 10^4
• 0 <= starti < endi <= 10^6

Solution Approach

This is a classic interval scheduling problem that can be solved efficiently using a min-heap (priority queue).

Key Insight

Use a min-heap to track when conference rooms become available!

The heap stores end times of ongoing meetings. When a new meeting arrives:

• If the earliest ending meeting (heap top) ends before the new meeting starts, reuse that room
• Otherwise, allocate a new room

The maximum heap size represents the minimum rooms needed.

Why Min-Heap?

We need to know which room becomes free earliest. A min-heap gives us the minimum end time in O(1) time.

Algorithm Steps

1. Sort intervals by start time (process chronologically)
2. Initialize min-heap (priority queue)
3. Add first meeting's end time to heap
4. For each subsequent meeting:
   • If heap.peek() <= meeting.start: A room is free! Remove from heap (reuse room)
   • Add current meeting's end time to heap
5. Return heap size (= rooms needed)

Example Walkthrough

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

1. Sort by start: Already sorted
2. Meeting [0,30]: Add end time 30 to heap. Heap: [30], Rooms: 1
3. Meeting [5,10]:
   • Check: 30 > 5 (no room free)
   • Add 10 to heap. Heap: [10, 30], Rooms: 2
4. Meeting [15,20]:
   • Check: 10 <= 15 (room is free!)
   • Remove 10, add 20. Heap: [20, 30], Rooms: 2

Result: 2 rooms minimum

Why Sorting by Start Time?

Processing meetings in chronological order ensures we allocate rooms optimally. We always know all previous meetings have been considered.

Time & Space Complexity

• Time Complexity: O(n log n)

  • Sorting: O(n log n)
  • Heap operations: O(n log n) - n insertions/deletions, each O(log n)
  • Total: O(n log n)

• Space Complexity: O(n)

  • Min-heap can store up to n meetings in worst case
  • Sorting may use O(log n) to O(n) additional space

Java Solution (Min-Heap)

import java.util.*;

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

        // Sort by start time
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        // Min-heap to track end times of meetings
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Add first meeting's end time
        minHeap.add(intervals[0][1]);

        // Process remaining meetings
        for (int i = 1; i < intervals.length; i++) {
            // If earliest ending meeting ends before current starts
            // we can reuse that room
            if (minHeap.peek() <= intervals[i][0]) {
                minHeap.poll();
            }

            // Add current meeting's end time
            minHeap.add(intervals[i][1]);
        }

        // Size of heap = number of rooms needed
        return minHeap.size();
    }
}

Python Solution (Min-Heap)

import heapq

def minMeetingRooms(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0

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

    # Min-heap to track end times
    min_heap = []

    # Add first meeting's end time
    heapq.heappush(min_heap, intervals[0][1])

    # Process remaining meetings
    for i in range(1, len(intervals)):
        # If earliest ending meeting ends before current starts
        if min_heap[0] <= intervals[i][0]:
            heapq.heappop(min_heap)

        # Add current meeting's end time
        heapq.heappush(min_heap, intervals[i][1])

    # Heap size = rooms needed
    return len(min_heap)

Alternative Approach: Chronological Ordering

Another elegant solution using start and end time arrays:

public int minMeetingRooms(int[][] intervals) {
    int n = intervals.length;
    int[] start = new int[n];
    int[] end = new int[n];

    // Separate start and end times
    for (int i = 0; i < n; i++) {
        start[i] = intervals[i][0];
        end[i] = intervals[i][1];
    }

    // Sort both arrays
    Arrays.sort(start);
    Arrays.sort(end);

    int rooms = 0;
    int endPtr = 0;

    // For each start time
    for (int i = 0; i < n; i++) {
        // If meeting starts after earliest end, reuse room
        if (start[i] >= end[endPtr]) {
            endPtr++;
        } else {
            // Need a new room
            rooms++;
        }
    }

    return rooms;
}

Time Complexity: O(n log n) Space Complexity: O(n)

This approach is elegant but the min-heap solution is more intuitive!

Related Problems

• Meeting Rooms (LeetCode 252): Check if person can attend all meetings
• Merge Intervals (LeetCode 56): Merge overlapping intervals
• Non-overlapping Intervals (LeetCode 435): Minimum removals
• My Calendar I (LeetCode 729): Book events without double booking
• Car Pooling (LeetCode 1094): Similar interval problem with capacity

Pattern Recognition

This problem demonstrates:

• Min-Heap / Priority Queue pattern
• Interval Scheduling optimization
• Greedy approach with data structure support
• Chronological processing (sort by time)

Common Mistakes

1. ❌ Not sorting by start time first
2. ❌ Using max-heap instead of min-heap
3. ❌ Checking all pairs: O(n²) instead of O(n log n)
4. ❌ Forgetting to poll from heap when room becomes free
5. ❌ Confusing with Meeting Rooms I (overlap check vs room count)

Tips for Interviews

• Explain why min-heap is perfect for this problem
• Mention the alternative chronological ordering approach
• Time complexity is O(n log n) due to sorting and heap
• Heap size never exceeds n (number of meetings)
• Compare with Meeting Rooms I as warm-up
• Draw a timeline diagram to visualize
• Discuss real-world applications (conference room booking, resource allocation)