Meeting Rooms II

Find minimum number of meeting rooms required using heap

Language Selection

Choose your preferred programming language

Showing: Python

Meeting Rooms II

Problem Statement

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

Input/Output Specifications

  • Input:
    • intervals: Array of intervals where each interval is [start_time, end_time]
  • Output: Integer representing minimum number of rooms needed

Constraints

  • 1 <= intervals.length <= 10^4
  • 0 <= start_i < end_i <= 10^6

Examples

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation: 
Meeting 1: [0,30]
Meeting 2: [5,10] - needs new room (overlaps with meeting 1)
Meeting 3: [15,20] - can use room from meeting 2 (ends at 10)
Minimum rooms needed: 2

Example 2:

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

Example 3:

Input: intervals = [[9,10],[4,9],[4,17]]
Output: 2
Explanation: [4,9] and [4,17] overlap, need 2 rooms.

Solution Approaches

Approach 1: Min-Heap (Optimal)

Algorithm Explanation:

  1. Sort meetings by start time
  2. Use min-heap to track end times of ongoing meetings
  3. For each meeting:
    • Remove meetings that ended before current start time
    • Add current meeting’s end time to heap
    • Track maximum heap size (concurrent meetings)

Implementation:

Python:

import heapq

def min_meeting_rooms(intervals):
    """
    Find minimum meeting rooms using min-heap
    Time: O(n log n)
    Space: O(n)
    """
    if not intervals:
        return 0
    
    # Sort meetings by start time
    intervals.sort(key=lambda x: x[0])
    
    # Min-heap to track end times of ongoing meetings
    heap = []
    
    for start, end in intervals:
        # Remove meetings that have ended
        if heap and heap[0] <= start:
            heapq.heappop(heap)
        
        # Add current meeting's end time
        heapq.heappush(heap, end)
    
    # Number of rooms needed is max concurrent meetings
    return len(heap)

# Alternative implementation with explicit room tracking
def min_meeting_rooms_v2(intervals):
    """
    Alternative with clearer room management
    Time: O(n log n)
    Space: O(n)
    """
    if not intervals:
        return 0
    
    intervals.sort()
    end_times = []  # Min-heap of meeting end times
    
    for start, end in intervals:
        # Check if any meeting has ended
        while end_times and end_times[0] <= start:
            heapq.heappop(end_times)
        
        # Assign current meeting to a room
        heapq.heappush(end_times, end)
    
    return len(end_times)

Java:

import java.util.*;

class Solution {
    /**
     * Find minimum meeting rooms using min-heap
     * Time: O(n log n)
     * Space: O(n)
     */
    public int minMeetingRooms(int[][] intervals) {
        if (intervals == null || intervals.length == 0) {
            return 0;
        }
        
        // Sort by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Min-heap to track end times
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        
        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            
            // Remove meetings that have ended
            if (!heap.isEmpty() && heap.peek() <= start) {
                heap.poll();
            }
            
            // Add current meeting's end time
            heap.offer(end);
        }
        
        return heap.size();
    }
}

Go:

import (
    "container/heap"
    "sort"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}

func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// minMeetingRooms - Find minimum meeting rooms using min-heap
// Time: O(n log n), Space: O(n)
func minMeetingRooms(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]
    })
    
    // Min-heap for end times
    minHeap := &MinHeap{}
    heap.Init(minHeap)
    
    for _, interval := range intervals {
        start, end := interval[0], interval[1]
        
        // Remove meetings that have ended
        if minHeap.Len() > 0 && (*minHeap)[0] <= start {
            heap.Pop(minHeap)
        }
        
        // Add current meeting's end time
        heap.Push(minHeap, end)
    }
    
    return minHeap.Len()
}

JavaScript:

class MinHeap {
    constructor() {
        this.heap = [];
    }
    
    push(val) {
        this.heap.push(val);
        this.bubbleUp();
    }
    
    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();
        
        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown();
        return min;
    }
    
    peek() {
        return this.heap[0];
    }
    
    size() {
        return this.heap.length;
    }
    
    bubbleUp() {
        let idx = this.heap.length - 1;
        while (idx > 0) {
            const parentIdx = Math.floor((idx - 1) / 2);
            if (this.heap[parentIdx] <= this.heap[idx]) break;
            [this.heap[parentIdx], this.heap[idx]] = [this.heap[idx], this.heap[parentIdx]];
            idx = parentIdx;
        }
    }
    
    bubbleDown() {
        let idx = 0;
        while (2 * idx + 1 < this.heap.length) {
            let minChildIdx = 2 * idx + 1;
            if (2 * idx + 2 < this.heap.length && 
                this.heap[2 * idx + 2] < this.heap[minChildIdx]) {
                minChildIdx = 2 * idx + 2;
            }
            
            if (this.heap[idx] <= this.heap[minChildIdx]) break;
            [this.heap[idx], this.heap[minChildIdx]] = [this.heap[minChildIdx], this.heap[idx]];
            idx = minChildIdx;
        }
    }
}

/**
 * Find minimum meeting rooms using min-heap
 * Time: O(n log n)
 * Space: O(n)
 */
function minMeetingRooms(intervals) {
    if (!intervals || intervals.length === 0) {
        return 0;
    }
    
    // Sort by start time
    intervals.sort((a, b) => a[0] - b[0]);
    
    const heap = new MinHeap();
    
    for (const [start, end] of intervals) {
        // Remove meetings that have ended
        if (heap.size() > 0 && heap.peek() <= start) {
            heap.pop();
        }
        
        // Add current meeting's end time
        heap.push(end);
    }
    
    return heap.size();
}

Approach 2: Event-Based Sweep Line

Algorithm Explanation:

  1. Create events for meeting start (+1 room) and end (-1 room)
  2. Sort all events by time
  3. Process events in order, tracking concurrent meetings
  4. Return maximum concurrent meetings seen

Implementation:

Python:

def min_meeting_rooms_sweep(intervals):
    """
    Find minimum rooms using sweep line algorithm
    Time: O(n log n)
    Space: O(n)
    """
    if not intervals:
        return 0
    
    events = []
    
    # Create start and end events
    for start, end in intervals:
        events.append((start, 1))   # Meeting starts
        events.append((end, -1))    # Meeting ends
    
    # Sort events by time, end events before start events for same time
    events.sort(key=lambda x: (x[0], x[1]))
    
    concurrent = 0
    max_rooms = 0
    
    for time, delta in events:
        concurrent += delta
        max_rooms = max(max_rooms, concurrent)
    
    return max_rooms

Key Insights

  • Heap Tracks Active Meetings: Min-heap stores end times of ongoing meetings
  • Room Reuse: Can reuse room when previous meeting ends before new one starts
  • Sorting Importance: Process meetings in chronological order
  • Concurrent Tracking: Maximum concurrent meetings = minimum rooms needed

Edge Cases

  1. No Intervals: Return 0
  2. Single Meeting: Return 1
  3. No Overlaps: Return 1 (can reuse same room)
  4. All Overlap: Return number of meetings
  5. Adjacent Meetings: Meeting ending at time t, next starting at time t (no overlap)

Test Cases

def test_min_meeting_rooms():
    # Example 1
    assert min_meeting_rooms([[0,30],[5,10],[15,20]]) == 2
    
    # Example 2 - no overlap
    assert min_meeting_rooms([[7,10],[2,4]]) == 1
    
    # All overlap
    assert min_meeting_rooms([[1,5],[2,6],[3,7]]) == 3
    
    # Adjacent meetings (no overlap)
    assert min_meeting_rooms([[1,2],[2,3],[3,4]]) == 1
    
    # Single meeting
    assert min_meeting_rooms([[1,3]]) == 1
    
    # Empty input
    assert min_meeting_rooms([]) == 0
    
    # Complex case
    assert min_meeting_rooms([[9,10],[4,9],[4,17]]) == 2
    
    # Test sweep line approach
    assert min_meeting_rooms_sweep([[0,30],[5,10],[15,20]]) == 2
    assert min_meeting_rooms_sweep([[1,2],[2,3],[3,4]]) == 1
    
    print("All tests passed!")

test_min_meeting_rooms()

Interview Tips

  1. Visualize Timeline: Draw meetings on timeline to show overlaps
  2. Heap Intuition: Explain why min-heap tracks earliest ending meeting
  3. Room Reuse: Emphasize when rooms can be reused
  4. Alternative Approaches: Mention sweep line algorithm
  5. Edge Cases: Handle empty input and adjacent meetings correctly

Follow-up Questions

  1. Meeting Rooms I: Check if person can attend all meetings
  2. Room Assignment: Return which room each meeting should use
  3. Maximum Overlap: Find time with maximum concurrent meetings
  4. Resource Scheduling: Generalize to other resources beyond rooms
  5. Online Algorithm: Handle meetings arriving dynamically

Common Mistakes

  1. Wrong Sorting: Not sorting meetings by start time
  2. Overlap Definition: Confusing whether adjacent times count as overlap
  3. Heap Management: Incorrectly removing or adding meeting end times
  4. Edge Cases: Not handling empty input or single meeting
  5. Off-by-One: Incorrect comparison for meeting end vs start times

Concept Explanations

Min-Heap for Scheduling: The heap maintains end times of currently active meetings. When a new meeting starts, we check if any ongoing meeting has ended (can reuse room). The heap size represents current room usage.

Greedy Strategy: Always reuse the room that becomes available first (earliest end time). This minimizes the total number of rooms needed.

Sweep Line Alternative: Instead of using a heap, we can process all start/end events chronologically and track the running count of concurrent meetings. Both approaches achieve the same O(n log n) complexity.

When to Apply: Use this pattern for interval scheduling problems, resource allocation, or any problem involving overlapping ranges where you need to track maximum concurrent usage.