Meeting Rooms II

[!NOTE] This problem is a foundational “Interval” problem. It tests your ability to track concurrent events over time. The key is recognizing that we only care about when a room becomes free or when a new meeting starts.

---

1. Problem Definition

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

Example 1:

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

Example 2:

• Input: intervals = [[7,10],[2,4]]
• Output: 1

Constraints:

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

---

2. Interactive Analysis

0102030

Choose a strategy to see how rooms are allocated.

---

3. Intuition

The core challenge is finding the maximum number of overlapping intervals at any single point in time.

The Min-Heap Approach

If we sort meetings by start time, we can process them one by one. To know if we can reuse a room, we only need to know when the earliest-ending meeting finishes.

• If current_start >= earliest_end, we reuse that room and update its new end time.
• If not, we must open a new room. The Min-Heap keeps track of all room end times, with the earliest at the top.

The Two-Pointer (Chronological) Approach

Imagine a door to a building. Every start time is a person entering, and every end time is a person leaving.

• Sort starts and ends separately.
• When a person enters, check if anyone has left at or before that time.
• If someone left, we don’t need a new room (the “occupancy” count doesn’t increase).
• The maximum occupancy at any point is the answer.

---

4. Solutions

Java

Go

class Solution {
    /**
     * Approach 1: Min-Heap
     * Time: O(N log N) | Space: O(N)
     */
    public int minMeetingRoomsHeap(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return 0;
        
        // 1. Sort by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        // 2. Min-Heap stores end times of active meetings
        PriorityQueue<Integer> rooms = new PriorityQueue<>();
        
        rooms.add(intervals[0][1]);
        
        for (int i = 1; i < intervals.length; i++) {
            // If the earliest meeting is over, reuse the room
            if (rooms.peek() <= intervals[i][0]) {
                rooms.poll();
            }
            
            // Add current meeting's end time
            rooms.add(intervals[i][1]);
        }
        
        return rooms.size();
    }

    /**
     * Approach 2: Chronological Sorting (Two Pointers)
     * Time: O(N log N) | Space: O(N)
     */
    public int minMeetingRooms(int[][] intervals) {
        int n = intervals.length;
        int[] startTimes = new int[n];
        int[] endTimes = new int[n];

        for (int i = 0; i < n; i++) {
            startTimes[i] = intervals[i][0];
            endTimes[i] = intervals[i][1];
        }

        Arrays.sort(startTimes);
        Arrays.sort(endTimes);

        int rooms = 0, endIdx = 0;

        for (int startIdx = 0; startIdx < n; startIdx++) {
            // If a meeting ended before or when this one starts, reuse it
            if (startTimes[startIdx] >= endTimes[endIdx]) {
                rooms--;
                endIdx++;
            }
            // Always count the new meeting
            rooms++;
        }

        return rooms;
    }
}

import (
    "container/heap"
    "sort"
)

/**
 * Approach 1: Min-Heap
 */
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)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func minMeetingRoomsHeap(intervals [][]int) int {
    if len(intervals) == 0 { return 0 }
    
    // Sort by start time
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })
    
    h := &IntHeap{intervals[0][1]}
    heap.Init(h)
    
    for i := 1; i < len(intervals); i++ {
        // Reuse room if earliest end time <= current start
        if (*h)[0] <= intervals[i][0] {
            heap.Pop(h)
        }
        heap.Push(h, intervals[i][1])
    }
    
    return h.Len()
}

/**
 * Approach 2: Chronological Sorting
 */
func minMeetingRooms(intervals [][]int) int {
    n := len(intervals)
    starts := make([]int, n)
    ends := make([]int, n)
    
    for i, interval := range intervals {
        starts[i] = interval[0]
        ends[i] = interval[1]
    }
    
    sort.Ints(starts)
    sort.Ints(ends)
    
    rooms := 0
    endIdx := 0
    for startIdx := 0; startIdx < n; startIdx++ {
        if starts[startIdx] >= ends[endIdx] {
            rooms--
            endIdx++
        }
        rooms++
    }
    return rooms
}

---

5. Complexity Analysis

Strategy	Time Complexity	Space Complexity	Notes
Min-Heap	$O(N \log N)$	$O(N)$	$N \log N$ for sorting, then $N \log N$ for heap operations.
Chronological Sort	$O(N \log N)$	$O(N)$	Two $O(N \log N)$ sorting steps, then one linear scan.