How to Solve: Meeting Rooms II (Minimum Platforms) – Complete Guide for FAANG Interviews

How to Solve: Meeting Rooms II (Minimum Platforms) – Complete Guide for FAANG Interviews

? Introduction

"This problem appears in 1 out of every 3 onsite interviews—master it, and you’ll prove you can handle real-world scheduling constraints with optimal efficiency."

? WHAT YOU NEED TO KNOW FIRST

Before tackling this problem, ensure you understand: 1. Sorting (custom comparators, stability) 2. Min-Heap (Priority Queue) (insertion, extraction, peek) 3. Two-Pointer Technique (for merging intervals)

? KEY TECHNIQUES & PATTERNS

? STEP-BY-STEP FRAMEWORK (Mental Checklist)

Follow these steps every time you see a "minimum platforms" or "meeting rooms" problem:

1. Clarify Input/Output
2. Confirm if intervals are [start, end] or [start, duration].
3. Ask if intervals are sorted (if not, sort them).

4. Ask if end time is inclusive/exclusive (usually exclusive).

5. Choose the Right Technique

6. If intervals are unsorted → Sort + Min-Heap (most common).
7. If intervals are sorted → Two-Pointer (Greedy) (faster, O(1) space).

8. If follow-up asks for "which rooms" → Track room assignments (use heap of room IDs).

9. Sort Intervals (If Needed)

10. Sort by start time (ascending).

11. If using two-pointer, sort start and end times separately.

12. Initialize Data Structures

13. Min-Heap: Store end times of ongoing meetings.

14. Two-Pointer: i (start pointer), j (end pointer), count = 0, max_count = 0.

15. Process Intervals

16. Min-Heap Approach:
    • For each meeting, if the earliest ending meeting ends before the current meeting starts → reuse the room (pop from heap).
    • Push current meeting’s end time into the heap.
    • Track heap size (max size = answer).

17. Two-Pointer Approach:

    • If start[i] < end[j] → new meeting starts before one ends → increment count.
    • Else → a meeting ends → decrement count.
    • Track max_count.

18. Edge Cases

19. Empty input → return 0.
20. Single meeting → return 1.

21. All meetings at the same time → return n.

22. Optimize & Verify

23. Time: O(n log n) (sorting) + O(n log n) (heap) = O(n log n).
24. Space: O(n) (heap) or O(1) (two-pointer).
25. Test with:
    • [ [1, 2], [2, 3] ] → 1 (no overlap).
    • [ [1, 5], [2, 3], [4, 6] ] → 2 (overlap at 2-3 and 4-5).

? WORKED EXAMPLES

Example 1 – Basic (Min-Heap Approach)

Problem: Given an array of meeting intervals [start, end], find the minimum number of rooms required.

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

Step-by-Step Solution

1. Sort intervals by start time:
   [[0, 30], [5, 10], [15, 20]] (already sorted).
2. Initialize a min-heap to track end times.
3. Process each meeting:
4. [0, 30] → heap is empty → push 30 → heap = [30], rooms = 1.
5. [5, 10] → earliest end (30) > 5 → new room needed → push 10 → heap = [10, 30], rooms = 2.
6. [15, 20] → earliest end (10) < 15 → reuse room → pop 10, push 20 → heap = [20, 30], rooms = 2.
7. Max heap size = 2 → answer.

Python Code

import heapq

def minMeetingRooms(intervals):

    if not intervals:

        return 0


    # Sort by start time

    intervals.sort(key=lambda x: x[0])


    # Min-heap to track end times

    heap = []

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


    for i in range(1, len(intervals)):

        start, end = intervals[i]


        # Reuse the earliest ending room

        if heap[0] <= start:

            heapq.heappop(heap)


        heapq.heappush(heap, end)


    return len(heap)

Complexity

• Time: O(n log n) (sorting) + O(n log n) (heap operations) = O(n log n).
• Space: O(n) (heap).

Why This Works

• The heap tracks the earliest ending meeting, allowing us to reuse rooms efficiently.
• The size of the heap at any point = number of rooms in use.

Example 2 – Medium (Two-Pointer Approach)

Problem: Same as above, but intervals are already sorted.

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

Step-by-Step Solution

1. Extract start and end times:
2. starts = [0, 5, 15]
3. ends = [10, 20, 30] (sorted).
4. Initialize two pointers (i, j) and counters:
5. i = 0, j = 0, count = 0, max_count = 0.
6. Process while i < n and j < n:
7. If starts[i] < ends[j] → new meeting starts before one ends → count++, i++.
   • 0 < 10 → count = 1, i = 1.
   • 5 < 10 → count = 2, i = 2.
8. Else → a meeting ends → count--, j++.
   • 15 > 10 → count = 1, j = 1.
   • 15 < 20 → count = 2, i = 3.
9. Update max_count = max(max_count, count).
10. Final max_count = 2 → answer.

Python Code

def minMeetingRooms(intervals):

    if not intervals:

        return 0


    starts = sorted([i[0] for i in intervals])

    ends = sorted([i[1] for i in intervals])


    i = j = count = max_count = 0


    while i < len(intervals):

        if starts[i] < ends[j]:

            count += 1

            i += 1

            max_count = max(max_count, count)

        else:

            count -= 1

            j += 1


    return max_count

Complexity

• Time: O(n log n) (sorting) + O(n) (two-pointer) = O(n log n).
• Space: O(n) (for starts and ends) or O(1) if input is already sorted.

Why This Works

• The two-pointer approach avoids the heap, reducing space complexity.
• It counts overlaps by comparing start and end times in order.

Example 3 – Hard (Follow-Up: Track Room Assignments)

Problem: Return which rooms are assigned to which meetings (not just the count).

Input: intervals = [[0, 30], [5, 10], [15, 20]] Output: [[0, 30], [5, 10]], [[15, 20]] (Room 1: [0,30] and [15,20], Room 2: [5,10])

Step-by-Step Solution

1. Sort intervals by start time.
2. Use a min-heap of (end_time, room_id).
3. For each meeting:
4. If the earliest ending meeting ends before the current meeting starts → reuse its room.
5. Else → assign a new room.
6. Track assignments in a dictionary.

Python Code

import heapq

def assignMeetingRooms(intervals):

    if not intervals:

        return []


    intervals.sort(key=lambda x: x[0])

    heap = []

    room_assignments = {}

    room_id = 0


    for start, end in intervals:

        if heap and heap[0][0] <= start:

            # Reuse the room

            _, reused_room = heapq.heappop(heap)

            room_assignments[reused_room].append([start, end])

            heapq.heappush(heap, (end, reused_room))

        else:

            # Assign a new room

            room_assignments[room_id] = [[start, end]]

            heapq.heappush(heap, (end, room_id))

            room_id += 1


    return list(room_assignments.values())

Complexity

• Time: O(n log n) (sorting + heap operations).
• Space: O(n) (heap + dictionary).

Why This Works

• The heap tracks both end time and room ID, allowing room reuse.
• The dictionary maps rooms to their meetings, providing the required output.

❌ Common Mistakes

? INTERVIEW TrapS

? 1-Minute Recap (Closing Script)

"Alright, let’s lock this in. When you see ‘Meeting Rooms II’ or ‘Minimum Platforms’: 1. Sort intervals by start time—always. 2. Use a min-heap to track end times. If the earliest ending meeting ends before the next starts, reuse the room. Otherwise, allocate a new one. 3. Two-pointer is faster if input is sorted—compare start and end times to count overlaps. 4. Edge cases: Empty input? Single meeting? All meetings at once? Handle them. 5. Follow-ups: Track room assignments? Use a heap with room IDs. Priorities? Switch to a max-heap.

You’ve got this. Walk in, sort, heap, and crush it."

? Final Notes

• Practice Variations:
• LeetCode 253. Meeting Rooms II
• LeetCode 252. Meeting Rooms (easier variant)
• GeeksforGeeks: Minimum Platforms
• Whiteboard Tip: Draw a timeline and mark overlaps visually before coding.