💬 Discord
Sign In
NeetCode #837LC-253MediumIntervalsBlind 75NC 150NC 250NC Algo100
← Back to All Problems

#837 · #253 · Meeting Rooms II(会议室 II)

📌 Problem Statement & Constraints

You are given an array of meeting time intervals intervals. Return the minimum number of conference rooms required to hold all meetings. Constraints: 0 <= intervals.length <= 10^4, 0 <= intervals[i][0] < intervals[i][1] <= 10^6.

💡 Core Algorithmic Approaches

  1. The answer is the maximum number of meetings happening simultaneously, i.e. the maximum overlap depth.
  2. Sort by start, then sweep with a min-heap of end times representing rooms in use.
  3. Before seating a meeting, pop every end time that is at or before the new start -- those rooms are free and can be reused.
  4. Push the new end time; the heap size after each step is the rooms in use, and its maximum is the answer.

💻 Benchmark Python3 Implementation

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        import heapq
        intervals.sort(key=lambda x: x[0])
        heap = []                               # end times of meetings in progress
        for s, e in intervals:
            if heap and heap[0] <= s:
                heapq.heappop(heap)             # a room frees up at time s
            heapq.heappush(heap, e)
        return len(heap)


# Sweep-line variant: +1 at each start, -1 at each end, then track the running max
class Solution2:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        events = []
        for s, e in intervals:
            events.append((s, 1))
            events.append((e, -1))
        events.sort()                           # ends (-1) sort before starts (+1) on ties
        cur = ans = 0
        for _, d in events:
            cur += d
            ans = max(ans, cur)
        return ans

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): sorting plus O(log n) heap operations per interval.
💾 Space Complexity
O(n): the heap (or the events array in the sweep-line variant).

⚠️ Interview Pitfalls & Follow-ups

  • Using heap[0] < s: a room that frees exactly at the start time is reusable, so the test is <=.
  • Popping all expired rooms instead of one: one room is enough to seat the current meeting; popping more would still be correct for the count but is unnecessary work.
  • Sorting events with starts before ends on ties: in the sweep-line variant the -1 end event must come first, which tuple ordering (time, delta) gives automatically.
  • Assuming the answer is len(intervals): rooms are reused, so the answer is the peak overlap, which can be much smaller.