LeetCode 253 - Meeting Rooms II

The problem gives us a list of meeting intervals where each interval is represented as [start, end]. Each interval describes the time range during which a meeting occupies a conference room.

leetcodemediumarraytwo-pointersgreedysortingheap-(priority-queue)prefix-sum

LeetCode Problem 253

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Greedy, Sorting, Heap (Priority Queue), Prefix Sum

Solution

Problem Understanding

The problem gives us a list of meeting intervals where each interval is represented as [start, end]. Each interval describes the time range during which a meeting occupies a conference room. The goal is to determine the minimum number of conference rooms needed so that all meetings can take place without conflicts.

A room can host multiple meetings as long as their times do not overlap. If one meeting ends exactly when another begins, the same room can be reused because the intervals are considered non-overlapping in that case.

For example, if we have meetings [[0,30],[5,10],[15,20]], the meeting [0,30] overlaps with both [5,10] and [15,20]. At time 5, two meetings are active simultaneously, which means at least two rooms are required.

The input size can be as large as 10^4 intervals, which means an inefficient quadratic solution may become too slow. The interval values themselves can be large, up to 10^6, but that does not matter much because we are mainly concerned with ordering and overlap relationships.

Several edge cases are important to recognize early:

  • Meetings that do not overlap at all should only require one room.
  • Meetings that all overlap completely require as many rooms as there are meetings.
  • Meetings that touch at boundaries, such as [1,5] and [5,10], should reuse the same room.
  • The intervals are not guaranteed to be sorted.
  • There is always at least one interval.

Approaches

Brute Force Approach

A straightforward approach is to compare every meeting against every other meeting and determine how many meetings overlap at each point in time. One possible implementation is to track room assignments manually and try to place each meeting into an existing room by checking all previously assigned meetings.

This works because every overlap relationship is explicitly examined. If no existing room can accommodate a meeting, we allocate a new room.

However, this approach becomes inefficient because for every meeting we may need to scan all currently allocated rooms and potentially all meetings inside them. In the worst case, this leads to quadratic time complexity.

With up to 10^4 meetings, an O(n^2) algorithm can become too slow.

Optimal Approach

The key observation is that we only care about how many meetings are active simultaneously at any moment.

If we process meetings in chronological order, we can track when rooms become available. The best way to do this is:

  1. Sort meetings by start time.
  2. Keep track of the earliest ending meeting currently using a room.
  3. If the next meeting starts after or exactly when the earliest meeting ends, that room can be reused.
  4. Otherwise, we need a new room.

A min-heap is ideal here because it efficiently gives us the meeting with the earliest ending time.

The heap represents all currently occupied rooms. Its size at any moment tells us how many rooms are in use.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Explicitly checks overlaps between meetings
Optimal O(n log n) O(n) Uses sorting and a min-heap of end times

Algorithm Walkthrough

  1. Sort all meeting intervals by their start times.

Sorting ensures we process meetings in chronological order. This allows us to decide whether a meeting can reuse an existing room or needs a new one. 2. Create a min-heap to store meeting end times.

The heap tracks the rooms currently in use. The smallest end time is always at the top, which tells us which room becomes free first. 3. Add the end time of the first meeting to the heap.

At least one room is required for the first meeting. 4. Iterate through the remaining meetings one by one.

For each meeting, compare its start time with the smallest end time in the heap. 5. If the meeting starts after or exactly when the earliest meeting ends, reuse that room.

Remove the earliest end time from the heap because that meeting has finished. 6. Push the current meeting's end time into the heap.

This marks the room as occupied until the current meeting ends. 7. Continue until all meetings are processed. 8. The size of the heap represents the number of rooms currently in use, and the maximum size reached is the minimum number of rooms required.

In this implementation, the final heap size after processing all intervals gives the correct answer because we only remove rooms when they become available.

Why it works

The algorithm maintains the invariant that the heap contains exactly the end times of meetings currently occupying rooms. By always removing the earliest ending meeting first, we greedily reuse rooms whenever possible. Since no room can be reused before its meeting ends, and we always choose the earliest available room, the algorithm minimizes the total number of rooms needed.

Python Solution

from typing import List
import heapq

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

        intervals.sort(key=lambda interval: interval[0])

        min_heap = []

        heapq.heappush(min_heap, intervals[0][1])

        for start, end in intervals[1:]:
            if start >= min_heap[0]:
                heapq.heappop(min_heap)

            heapq.heappush(min_heap, end)

        return len(min_heap)

The implementation begins by sorting the intervals according to start time. This guarantees that meetings are processed in chronological order.

A min-heap named min_heap stores end times of active meetings. The smallest end time is always available at index 0, allowing us to efficiently determine which room becomes free first.

The first meeting always requires one room, so its end time is pushed into the heap immediately.

For every subsequent meeting, we compare its start time with the smallest end time in the heap:

  • If the start time is greater than or equal to the earliest end time, the room can be reused, so we pop the heap.
  • Regardless of reuse or allocation, we push the current meeting's end time into the heap.

At the end, the heap size equals the number of rooms needed.

Go Solution

package main

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)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func minMeetingRooms(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}

	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	heap.Push(minHeap, intervals[0][1])

	for _, interval := range intervals[1:] {
		start := interval[0]
		end := interval[1]

		if start >= (*minHeap)[0] {
			heap.Pop(minHeap)
		}

		heap.Push(minHeap, end)
	}

	return minHeap.Len()
}

The Go implementation follows the same logic as the Python solution but requires an explicit heap implementation using the container/heap package.

Go does not provide a built-in min-heap for integers, so we define a custom MinHeap type implementing the required interface methods.

Unlike Python, Go distinguishes between slices and heap operations explicitly. We use pointer receivers for Push and Pop because heap operations modify the underlying slice.

Integer overflow is not a concern because the interval values are well within Go's integer range.

Worked Examples

Example 1

Input:

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

After sorting:

[[0,30],[5,10],[15,20]]
Step Current Meeting Heap Before Action Heap After
1 [0,30] [] Add end time 30 [30]
2 [5,10] [30] 5 < 30, need new room [10,30]
3 [15,20] [10,30] 15 >= 10, reuse room [20,30]

Final heap size:

2

Answer:

2

Example 2

Input:

intervals = [[7,10],[2,4]]

After sorting:

[[2,4],[7,10]]
Step Current Meeting Heap Before Action Heap After
1 [2,4] [] Add end time 4 [4]
2 [7,10] [4] 7 >= 4, reuse room [10]

Final heap size:

1

Answer:

1

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, and each heap operation costs O(log n)
Space O(n) The heap may contain all meetings in the worst case

The sorting step requires O(n log n) time. Each meeting is inserted into the heap once, and possibly removed once, with each heap operation taking O(log n) time.

The heap can grow to size n when all meetings overlap, so the space complexity is O(n).

Test Cases

from typing import List
import heapq

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

        intervals.sort(key=lambda interval: interval[0])

        min_heap = []

        heapq.heappush(min_heap, intervals[0][1])

        for start, end in intervals[1:]:
            if start >= min_heap[0]:
                heapq.heappop(min_heap)

            heapq.heappush(min_heap, end)

        return len(min_heap)

solution = Solution()

assert solution.minMeetingRooms([[0,30],[5,10],[15,20]]) == 2  # overlapping meetings
assert solution.minMeetingRooms([[7,10],[2,4]]) == 1  # non-overlapping meetings
assert solution.minMeetingRooms([[1,5],[5,10]]) == 1  # boundary reuse
assert solution.minMeetingRooms([[1,10],[2,9],[3,8]]) == 3  # complete overlap
assert solution.minMeetingRooms([[1,2]]) == 1  # single meeting
assert solution.minMeetingRooms([[1,4],[2,5],[7,9]]) == 2  # partial overlap
assert solution.minMeetingRooms([[6,7],[2,4],[8,12]]) == 1  # unsorted input
assert solution.minMeetingRooms([[1,5],[2,6],[3,7],[4,8]]) == 4  # all overlap
assert solution.minMeetingRooms([[0,1],[1,2],[2,3],[3,4]]) == 1  # chain reuse
assert solution.minMeetingRooms([[13,15],[1,13]]) == 1  # exact boundary reuse
Test Why
[[0,30],[5,10],[15,20]] Standard overlapping example
[[7,10],[2,4]] No overlap case
[[1,5],[5,10]] Verifies boundary reuse
[[1,10],[2,9],[3,8]] Every meeting overlaps
[[1,2]] Smallest valid input
[[1,4],[2,5],[7,9]] Mixed overlap and reuse
[[6,7],[2,4],[8,12]] Confirms sorting works
[[1,5],[2,6],[3,7],[4,8]] Maximum simultaneous overlap
[[0,1],[1,2],[2,3],[3,4]] Continuous room reuse
[[13,15],[1,13]] End equals start edge case

Edge Cases

One important edge case is meetings that touch exactly at their boundaries, such as [[1,5],[5,10]]. A common mistake is using a strict greater-than comparison instead of greater-than-or-equal. If the implementation checks start > end rather than start >= end, it incorrectly allocates an extra room. This solution correctly reuses the room because it allows reuse when the previous meeting ends exactly at the new meeting's start time.

Another important case is when all meetings overlap completely, such as [[1,10],[2,9],[3,8]]. In this situation, every meeting requires its own room because none can reuse an existing one. The heap grows to contain all active meetings, and the algorithm correctly returns the total number of meetings.

Unsorted input is also a major source of bugs. The intervals may arrive in arbitrary order, and overlap decisions only work correctly when meetings are processed chronologically. The implementation explicitly sorts intervals by start time before any processing occurs, ensuring correctness regardless of input order.

A final subtle edge case is a single meeting. Some implementations incorrectly assume multiple intervals exist and may attempt to access nonexistent elements. This solution handles the case naturally because the heap is initialized with the first interval, and the loop over remaining intervals simply does not execute.