253. Meeting Rooms II

At a Glance

Topic: intervals
Pattern: Top-K / Heap (min-heap of end times) on timeline
Difficulty: Medium
Companies: Google, Amazon, Bloomberg, Microsoft, Facebook
Frequency: Very High
LeetCode: 253

Problem (one-liner)

Given meeting intervals, return the minimum number of conference rooms needed so no overlapping meetings share a room. Input: intervals. Output: positive integer count.

Recognition Cues

“Minimum rooms” / “maximum concurrent meetings”
Sweep events or heap of meeting end times
Greedy: assign room ending soonest (min-heap by end time)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Timeline sweep with multiset — O(n log n) time.
Min-heap of end times — O(n log n) time / O(n) space. <- pick this in interview.

Optimal Solution

Go

package main

import (
	"container/heap"
	"sort"
)

type IntHeap []int

func (heap IntHeap) Len() int           { return len(heap) }
func (heap IntHeap) Less(left int, right int) bool {
	return heap[left] < heap[right]
}
func (heap IntHeap) Swap(left int, right int) {
	heap[left], heap[right] = heap[right], heap[left]
}

func (heap *IntHeap) Push(value interface{}) {
	*heap = append(*heap, value.(int))
}

func (heap *IntHeap) Pop() interface{} {
	old := *heap
	length := len(old)
	value := old[length-1]
	*heap = old[:length-1]
	return value
}

func minMeetingRooms(intervals [][]int) int {
	if len(intervals) == 0 {
		return 0
	}
	sort.Slice(intervals, func(left int, right int) bool {
		if intervals[left][0] == intervals[right][0] {
			return intervals[left][1] < intervals[right][1]
		}
		return intervals[left][0] < intervals[right][0]
	})
	endTimes := &IntHeap{}
	heap.Init(endTimes)
	for _, meeting := range intervals {
		start := meeting[0]
		end := meeting[1]
		if endTimes.Len() > 0 && (*endTimes)[0] <= start {
			heap.Pop(endTimes)
		}
		heap.Push(endTimes, end)
	}
	return endTimes.Len()
}

JavaScript

class MinHeap {
	constructor() {
		this.values = [];
	}
	push(value) {
		this.values.push(value);
		this.bubbleUp(this.values.length - 1);
	}
	pop() {
		if (this.values.length === 0) return undefined;
		const top = this.values[0];
		const last = this.values.pop();
		if (this.values.length > 0) {
			this.values[0] = last;
			this.bubbleDown(0);
		}
		return top;
	}
	peek() {
		return this.values[0];
	}
	get length() {
		return this.values.length;
	}
	bubbleUp(index) {
		while (index > 0) {
			const parent = Math.floor((index - 1) / 2);
			if (this.values[parent] <= this.values[index]) break;
			[this.values[parent], this.values[index]] = [
				this.values[index],
				this.values[parent],
			];
			index = parent;
		}
	}
	bubbleDown(index) {
		const length = this.values.length;
		while (true) {
			const left = index * 2 + 1;
			const right = index * 2 + 2;
			let smallest = index;
			if (left < length && this.values[left] < this.values[smallest]) {
				smallest = left;
			}
			if (right < length && this.values[right] < this.values[smallest]) {
				smallest = right;
			}
			if (smallest === index) break;
			[this.values[index], this.values[smallest]] = [
				this.values[smallest],
				this.values[index],
			];
			index = smallest;
		}
	}
}

function minMeetingRooms(intervals) {
	if (intervals.length === 0) return 0;
	const sorted = [...intervals].sort((left, right) => {
		if (left[0] === right[0]) return left[1] - right[1];
		return left[0] - right[0];
	});
	const endTimes = new MinHeap();
	for (const meeting of sorted) {
		const start = meeting[0];
		const end = meeting[1];
		if (endTimes.length > 0 && endTimes.peek() <= start) {
			endTimes.pop();
		}
		endTimes.push(end);
	}
	return endTimes.length;
}