Skip to main content

🟨 Meeting Rooms II (#253) 🔒

🔗 Problem Link​

📋 Problem Statement​

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

Note: This is a premium LeetCode problem, but available for free on NeetCode.

💡 Examples​

Example 1​

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2​

Input: intervals = [[7,10],[2,4]]
Output: 1

🔑 Key Insights & Approach​

Core Observation: Track concurrent meetings using start/end times or min heap.

Why Min Heap?

  • O(n log n) time
  • Track earliest ending meeting
  • Add meeting if room available, otherwise need new room

Pattern: "Concurrent Intervals" using heap or timeline.

🐍 Solution: Python​

Approach: Min Heap​

Time Complexity: O(n log n) | Space Complexity: O(n)

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 x: x[0])
        heap = []  # min heap of end times

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

        for i in range(1, len(intervals)):
            if intervals[i][0] >= heap[0]:
                heapq.heappop(heap)

            heapq.heappush(heap, intervals[i][1])

        return len(heap)

Approach 2: Timeline​

Time Complexity: O(n log n) | Space Complexity: O(n)

from typing import List

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        start = sorted([i[0] for i in intervals])
        end = sorted([i[1] for i in intervals])

        rooms = 0
        max_rooms = 0
        s, e = 0, 0

        while s < len(start):
            if start[s] < end[e]:
                rooms += 1
                max_rooms = max(max_rooms, rooms)
                s += 1
            else:
                rooms -= 1
                e += 1

        return max_rooms

🔵 Solution: Golang​

Approach: Min Heap​

Time Complexity: O(n log n) | Space Complexity: O(n)

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
}

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

    h := &MinHeap{}
    heap.Init(h)
    heap.Push(h, intervals[0][1])

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] >= (*h)[0] {
            heap.Pop(h)
        }
        heap.Push(h, intervals[i][1])
    }

    return h.Len()
}

📚 References​