LeetCode 253: Meeting Rooms II Solution in Python – A Step-by-Step Guide

What Is LeetCode 253: Meeting Rooms II?

In LeetCode 253: Meeting Rooms II, you’re given a list of meeting time intervals, where each interval is a pair [start, end] representing the start and end times of a meeting. Your task is to find the minimum number of meeting rooms needed so all meetings can occur without conflicts. This problem builds on LeetCode 252: Meeting Rooms, moving from a yes-or-no check to counting the resources required.

Problem Statement

• Input: A list of intervals intervals, where each interval is [start, end].
• Output: An integer—the minimum number of meeting rooms needed.
• Rules: Meetings overlap if one starts before another ends; overlapping meetings need separate rooms.

Constraints

• Number of intervals: 0 to 10^4.
• Start and end times: 0 to 10^6.
• start < end for each interval.

Examples

• Input: intervals = [[0,30], [5,10], [15,20]]
• Output: 2 (0-30 overlaps with 5-10, but 15-20 fits with 5-10).
• Input: intervals = [[7,10], [2,4]]
• Output: 1 (no overlaps).
• Input: intervals = []
• Output: 0 (no meetings, no rooms).

Understanding the Problem: Counting Rooms

To solve LeetCode 253: Meeting Rooms II in Python, we need to figure out how many meetings happen at the same time at their peak—that’s the number of rooms we’ll need. Two intervals [s1, e1] and [s2, e2] overlap if s1 < e2 and s2 < e1. A naive approach—checking all pairs—is too slow. We’ll use two methods: 1. Best Solution (Chronological Sorting with Heap): O(n log n) time—fast and dynamic. 2. Alternative Solution (Start-End Sorting): O(n log n) time—simple but insightful.

Let’s dive into the best solution with extra detail for beginners.

Best Solution: Chronological Sorting with Heap

Why This Is the Best Solution

The chronological sorting with heap approach is the top choice for LeetCode 253 because it runs in O(n log n) time, efficiently tracks active meetings using a min-heap, and adapts to real-time scheduling needs. It’s beginner-friendly once explained and balances speed with clarity, making it the go-to solution.

How It Works

Picture this solution as managing a busy conference center. You sort meetings by start time, like lining them up on a schedule, and use a “room tracker” (a min-heap) to keep tabs on when each room frees up. As meetings start, you assign rooms; as they end, you free rooms for reuse. Here’s how it works, step-by-step, explained simply for beginners:

• Step 1: Sort by Start Time:
• Take the list of intervals and sort them by start time.
• For example, [[0,30], [5,10], [15,20]] stays as is (already sorted).
• This puts meetings in the order they begin, so we can process them chronologically.
• Step 2: Use a Min-Heap for End Times:
• Create a min-heap (a tool that always gives you the smallest value first) to store the end times of meetings currently in progress.
• Think of it as a list of “when each room will be free.”
• Step 3: Process Each Meeting:
• For each meeting [start, end]:
• Check Free Rooms: Look at the heap. If the earliest end time (smallest in heap) is less than or equal to the new meeting’s start time, that room is free—remove that end time from the heap.
• Assign a Room: Add the new meeting’s end time to the heap. If you freed a room, you reuse it; if not, you’re using a new room.
• Step 4: Track Maximum Rooms:
• The size of the heap at any point is the number of rooms in use. The maximum size it ever reaches is the minimum rooms needed.
• Step 5: Handle Edge Cases:
• Empty list? Return 0—no rooms needed.

It’s like juggling meeting rooms: sort the schedule, free up rooms as meetings end, and add new ones as they start, keeping only the smallest pile of “end times” you need!

Step-by-Step Example

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

• Step 1: Sort by Start Time:
• Already sorted: [[0,30], [5,10], [15,20]].
• Step 2: Initialize Heap and Counter:
• Heap = [] (empty list of end times).
• Max rooms = 0.
• Step 3: Process Meetings:
• Meeting 1: [0,30]:
• Heap empty, no rooms to free.
• Add end time 30 → Heap = [30].
• Rooms in use = 1, max rooms = 1.
• Meeting 2: [5,10]:
• Check heap: 30 > 5 (no room free yet).
• Add end time 10 → Heap = [10, 30] (min-heap keeps smallest first).
• Rooms in use = 2, max rooms = 2.
• Meeting 3: [15,20]:
• Check heap: 10 < 15 (room frees up), remove 10 → Heap = [30].
• Add end time 20 → Heap = [20, 30].
• Rooms in use = 2, max rooms = 2 (reused a room, no increase).
• Step 4: Finish:
• Max rooms needed = 2.
• Result: 2.

Example: intervals = [[7,10], [2,4]]

• Step 1: Sort:
• Sorted: [[2,4], [7,10]].
• Step 2: Initialize:
• Heap = [], max rooms = 0.
• Step 3: Process:
• [2,4]: Heap = [4], rooms = 1, max = 1.
• [7,10]: 4 < 7, remove 4 → Heap = [], add 10 → Heap = [10], rooms = 1, max = 1.
• Result: 1.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeimport heapq

class Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # Step 1: Handle empty case
        if not intervals:
            return 0

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

        # Step 3: Set up our room tracker (min-heap)
        end_times = []  # Stores when each room frees up

        # Step 4: Process each meeting
        for start, end in intervals:
            # Step 5: Free up rooms if possible
            while end_times and end_times[0] <= start:
                # If a room’s meeting ended before this one starts, remove it
                heapq.heappop(end_times)

            # Step 6: Add new meeting’s end time
            heapq.heappush(end_times, end)

        # Step 7: Max size of heap is rooms needed
        return len(end_times)

• Time Complexity: O(n log n)—sorting plus heap operations.
• Space Complexity: O(n)—heap stores up to n end times.

This solution is like a smart office manager—keeping just enough rooms busy!

Alternative Solution: Start-End Sorting

Why an Alternative Approach?

The start-end sorting approach splits intervals into start and end events, sorts them, and counts rooms by tracking active meetings. It’s less dynamic but easier to visualize as a timeline, making it a good alternative for beginners.

How It Works

Imagine marking every start and end time on a number line, then walking through to see how many meetings are happening at once. Here’s how it works, explained simply:

• Step 1: Split Events:
• Create a list of events: (time, is_start).
• For [0,30], add (0, True) and (30, False).
• Step 2: Sort Events:
• Sort by time; if times tie, ends come before starts (to count correctly).
• Step 3: Count Rooms:
• Walk through events:
• Start (+1 room).
• End (-1 room).
• Track the maximum count of active meetings.

It’s like watching a live tally of people entering and leaving a room!

Step-by-Step Example

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

• Step 1: Split:
• (0, True), (30, False), (5, True), (10, False), (15, True), (20, False).
• Step 2: Sort:
• [(0, True), (5, True), (10, False), (15, True), (20, False), (30, False)].
• Step 3: Count:
• 0: +1 → 1 room.
• 5: +1 → 2 rooms (max so far).
• 10: -1 → 1 room.
• 15: +1 → 2 rooms.
• 20: -1 → 1 room.
• 30: -1 → 0 rooms.
• Result: Max = 2.

Code for Start-End Approach

Copy codeclass Solution:
    def minMeetingRooms(self, intervals: List[List[int]]) -> int:
        # Step 1: Handle empty case
        if not intervals:
            return 0

        # Step 2: Create events
        events = []
        for start, end in intervals:
            events.append((start, 1))  # 1 for start
            events.append((end, -1))  # -1 for end

        # Step 3: Sort events (end before start if tied)
        events.sort()

        # Step 4: Count rooms
        curr_rooms = 0
        max_rooms = 0
        for time, change in events:
            curr_rooms += change
            max_rooms = max(max_rooms, curr_rooms)

        return max_rooms

• Time Complexity: O(n log n)—sorting events.
• Space Complexity: O(n)—storing events.

It’s clear but uses more space.

Comparing the Two Solutions

• Best Solution (Heap):
• Pros: O(n log n), dynamic, O(n) space.
• Cons: Heap concept might be new.
• Alternative Solution (Start-End):
• Pros: Intuitive timeline, O(n log n).
• Cons: O(n) space for events.

Heap wins for adaptability.

Additional Examples and Edge Cases

No Overlaps

• [[1,2], [3,4]] → 1

All Overlap

• [[1,3], [1,4], [2,5]] → 3

Empty

• [] → 0

Both handle these well.

Complexity Breakdown

• Heap:
• Time: O(n log n)—sorting + heap.
• Space: O(n)—heap.
• Start-End:
• Time: O(n log n)—sorting.
• Space: O(n)—events.

Heap is more flexible.

Key Takeaways for Beginners

• Heap: Tracks earliest end efficiently.
• Sorting: Order simplifies overlap checks.
• Start-End: Timeline view is intuitive.
• Python Tip: heapq is your friend—see [Python Basics](/python/basics).

Final Thoughts: Book Rooms Like a Pro

LeetCode 253: Meeting Rooms II in Python is a fantastic scheduling challenge. The heap solution offers dynamic efficiency, while start-end sorting provides clarity. Want more? Try LeetCode 252: Meeting Rooms or LeetCode 435: Non-overlapping Intervals. Ready to manage? Head to Solve LeetCode 253 on LeetCode and book those rooms today!