NUHMAN.com

Introduction

LeetCode 253: Meeting Rooms II is a follow-up to the simpler Meeting Rooms I problem. Instead of checking for conflicts, we now need to calculate the minimum number of meeting rooms required to accommodate all meetings without conflicts.

This is a classic interval scheduling and heap problem often asked in interviews at top tech companies.

Problem Statement

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

Examples:

lua

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

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

Step-by-Step Solution in Python

Step 1: Sort the Intervals by Start Time

We need to process meetings in the order they begin, so we start by sorting the intervals by their start time.

Step 2: Use a Min-Heap to Track End Times

We use a min-heap (priority queue) to store the end times of ongoing meetings:

• If a new meeting starts after the earliest one ends → we can reuse that room
• Otherwise → allocate a new room

Step 3: Code It

python

import heapq

def minMeetingRooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0

    # Sort the meetings by start time
    intervals.sort(key=lambda x: x[0])

    # Initialize a min-heap with the end time of the first meeting
    min_heap = [intervals[0][1]]

    for i in range(1, len(intervals)):
        current_start = intervals[i][0]
        current_end = intervals[i][1]

        # If the current meeting starts after the earliest one ends
        if current_start >= min_heap[0]:
            heapq.heappop(min_heap)  # Reuse the room

        heapq.heappush(min_heap, current_end)  # Add current meeting's end time

    return len(min_heap)  # Number of rooms = size of heap

Explanation of the Code

1. Sort by Start Time:
2. Meetings are sorted so we always consider them in chronological order.
3. Min-Heap of End Times:
4. The heap keeps track of ongoing meetings by their end times. The top of the heap always gives us the earliest ending meeting.
5. Reusing Rooms:
6. If the current meeting starts after or exactly when the earliest one ends, pop that meeting (free up the room).
7. Add Current End Time:
8. Push the current meeting’s end time into the heap.
9. Final Answer:
10. The number of active rooms is the size of the heap after processing all meetings.

Example Walkthrough

Input: [[0,30],[5,10],[15,20]]

• After sorting: [[0,30], [5,10], [15,20]]
• Heap: [30] → Add 10 → [10, 30] → Add 20 (can't reuse) → [10, 30, 20]
• Pop 10, push 20 → Final Heap: [20, 30] → 2 rooms needed

Time and Space Complexity

• Time Complexity:
• O(n log n) for sorting
• O(n log n) for heap operations → total: O(n log n)
• Space Complexity:
• O(n) for heap to store end times

Conclusion

LeetCode 253 is an essential greedy + heap problem. By using a min-heap to track active meetings, we can efficiently allocate and reuse rooms while maintaining the correct count.

It’s commonly asked in interviews and builds on foundational concepts like sorting and heaps.