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

Edge Cases & Clarifying Questions

• What if the intervals array is empty?
  • Return 0 since no rooms are needed.
• Can intervals overlap exactly at the boundary (e.g., [1, 5] and [5, 10])?
  • Typically, if a meeting ends at the exact time another starts, we do not need an extra room (they can use the same room).
• Are the intervals sorted?
  • No, we should assume the input intervals are unsorted.

---

2. Interactive Analysis

0102030

Choose a strategy to see how rooms are allocated.

---

3. Intuition (The “Genesis”)

The core challenge is finding the maximum number of overlapping intervals at any single point in time. This is a classic “Sweep Line” or “Interval” pattern problem.

Brute Force Approach

A naive brute-force approach might be to simulate every minute from the earliest start time to the latest end time. For each minute, we could iterate through all intervals and count how many meetings are active. The maximum count at any minute would be the number of rooms needed. However, this is extremely inefficient. If time intervals span millions of minutes (e.g., 0 to 10^6), the time complexity would be $O(T \times N)$, where $T$ is the total time range. This would result in a Time Limit Exceeded (TLE) error. We need an approach that only looks at the critical points (when a meeting starts or ends).

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.

Common Pitfalls

• Forgetting to sort the intervals: A greedy or heap-based approach will fail if the intervals are not processed chronologically by start time.
• Incorrectly handling exact overlaps: If meeting A ends at 10 and meeting B starts at 10, they can share a room. Ensure your logic uses >= or <= correctly (e.g., startTimes[startIdx] >= endTimes[endIdx]).

---

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.