Meeting Rooms II

Problem statement

Given meeting intervals [start, end), find the minimum number of rooms required so that no two overlapping meetings share a room.

Example:

Input:

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

Expected output:

Why: [0, 30] overlaps both later meetings, so you need a second room.

Practice on LeetCode: Meeting Rooms II

Golang Solution

Sort by start time. Keep a min-heap of end times for meetings currently using a room. When a new meeting starts, if the earliest-ending room is free (end ≤ start), reuse it (pop); otherwise allocate another room (push). The heap size is the rooms in use; track the max.

Time: O(n log n) — sort plus heap operations
Space: O(n) — heap of end times

import "container/heap"

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]
    })

    maxRooms := 1
    h := &minHeap{} // Add first meeting's end time
    heap.Push(h, intervals[0][1])

    for i := 1; i < len(intervals); i++ {

        if (*h)[0] <= intervals[i][0] {
            heap.Pop(h)
        }

        heap.Push(h, intervals[i][1])

        maxRooms = max(maxRooms, h.Len())
    }

    return maxRooms
}

type minHeap []int

func (h minHeap) Swap(i, j int) {
    h[i], h[j] = h[j], h[i]
}

func (h minHeap) Less(i, j int) bool {
    return h[i] < h[j]
}

func (h minHeap) Len() int {
    return len(h)
}

func (h *minHeap) Push(node any) {
    *h = append(*h, node.(int))
}

func (h *minHeap) Pop() any {
    old := *h
    n := len(old)
    popped := (*h)[n-1]
    *h = (*h)[:n-1]
    return popped
}