Meeting Rooms II (Minimum Conference Rooms)

▶

Steps

setup

Sort intervals by start time

The algorithm sorts the input intervals by their start times to process meetings in chronological order.

💡 Sorting ensures meetings are handled in the order they begin, which is essential for correct room allocation.

Line:

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

💡 Sorted intervals allow a linear sweep to allocate rooms efficiently.

insert

Insert first meeting's end time into heap

Add the end time of the first meeting (30) to the min-heap, representing one room allocated.

💡 The heap tracks ongoing meetings by their end times; starting with the first meeting sets the baseline.

Line:

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

💡 Heap now contains [30], meaning one room is occupied until time 30.

compare

Compare second meeting start with earliest end time

Compare the start time of the second meeting (5) with the earliest end time in the heap (30).

💡 This comparison checks if the earliest room frees before the new meeting starts to decide room reuse.

Line:

if intervals[i][0] >= heap[0]:

💡 Since 5 < 30, the second meeting overlaps with the first, requiring a new room.

insert

Insert second meeting's end time into heap

Since the second meeting overlaps, add its end time (10) to the heap, allocating a new room.

💡 Adding the new meeting's end time tracks the additional room needed for overlapping meetings.

Line:

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

💡 Heap now contains [10,30], showing two rooms occupied ending at 10 and 30 respectively.

compare

Compare third meeting start with earliest end time

Compare the start time of the third meeting (15) with the earliest end time in the heap (10).

💡 This comparison determines if a room frees up before the third meeting starts.

Line:

if intervals[i][0] >= heap[0]:

💡 Since 15 >= 10, the room ending at 10 is now free and can be reused.

delete

Pop earliest end time from heap to free room

Remove the earliest end time (10) from the heap, indicating the room is freed for reuse.

💡 Popping the root frees a room, allowing the new meeting to reuse it instead of adding a new room.

Line:

heapq.heappop(heap)

💡 Heap now contains [30], representing one ongoing meeting occupying a room.

insert

Insert third meeting's end time into heap

Add the third meeting's end time (20) to the heap, representing the reused room now occupied until 20.

💡 Inserting the new end time updates the heap to track current room usage.

Line:

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

💡 Heap now contains [20, 30], showing two rooms occupied ending at 20 and 30.

traverse

All meetings processed; heap shows ongoing meetings

All meetings have been processed; the heap contains end times of meetings currently occupying rooms.

💡 The heap size now indicates the minimum number of rooms needed to accommodate all meetings.

Line:

return len(heap)

💡 Heap size is 2, meaning two rooms are required.

finalize

Calculate minimum number of rooms needed

Calculate the size of the heap, which represents the minimum number of rooms required.

💡 The heap size corresponds to the number of rooms occupied simultaneously at peak usage.

Line:

return len(heap)

💡 Heap size of 2 means two rooms are needed to accommodate all meetings without overlap.

final

Return the minimum number of rooms

Return the heap size as the minimum number of conference rooms required.

💡 Returning the heap size completes the algorithm, providing the final answer.

Line:

return len(heap)

💡 The final answer is 2, indicating two rooms are needed.

import heapq

def minMeetingRooms(intervals):
    if not intervals:
        return 0  # STEP 1: Handle empty input
    intervals.sort(key=lambda x: x[0])  # STEP 1: Sort intervals by start time
    heap = []
    heapq.heappush(heap, intervals[0][1])  # STEP 2: Push first meeting end time
    for i in range(1, len(intervals)):
        if intervals[i][0] >= heap[0]:  # STEP 3 & 5: Compare start with earliest end
            heapq.heappop(heap)  # STEP 6: Pop earliest end time if room frees
        heapq.heappush(heap, intervals[i][1])  # STEP 4 & 7: Push current meeting end time
    return len(heap)  # STEP 8: Return heap size as minimum rooms

intervals = [[0,30],[5,10],[15,20]]
print(minMeetingRooms(intervals))  # Output: 2

📊

Meeting Rooms II (Minimum Conference Rooms) - Watch the Algorithm Execute, Step by Step

Watching each heap operation and comparison reveals how the algorithm efficiently manages overlapping intervals to minimize rooms.

setupmin-heap

empty heap

insertmin-heap

30

0

comparemin-heap

30

0

insertmin-heapswap [0↔1]

10

0

30

1

comparemin-heap

10

0

30

1

extract_minmin-heap

30

0

insertmin-heap

20

0

30

1

peekmin-heap

20

0

30

1

peekmin-heap

20

0

30

1

Added: 2

finalmin-heap

20

0

30

1

Added: 2

Key Takeaways

✓ The min-heap efficiently tracks the earliest finishing meeting to decide room reuse.

This insight is hard to see from code alone because the heap operations abstract away the timing logic.

✓ Sorting intervals by start time enables a linear sweep to allocate rooms without backtracking.

Visualizing the sorted order clarifies why the algorithm processes meetings sequentially.

✓ When a meeting starts after the earliest end time, popping from the heap frees a room for reuse.

The trace shows exactly when and why a room is freed, which is subtle in code but clear visually.

Practice

1. You are given a list of trips, each with a number of passengers, a start location, and an end location. You need to determine if a vehicle with a fixed capacity can carry all passengers without exceeding capacity at any point along the route. Which algorithmic approach best guarantees an optimal and efficient solution?

easy

A. Brute force simulation by incrementing passenger count at every location for each trip

B. Greedy algorithm that picks trips with earliest end location first

C. Dynamic programming to find maximum passengers at each location using state transitions

D. Sweep line algorithm that processes passenger count changes at trip start and end points

Solution

1. Step 1: Understand problem constraints

   The problem requires tracking passenger counts over intervals defined by start and end locations.

2. Step 2: Identify suitable algorithm

   Sweep line processes events (passenger changes) in sorted order, efficiently tracking capacity usage without simulating every location.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sweep line handles interval events optimally [OK]

Hint: Intervals with start/end events -> sweep line [OK]

Common Mistakes:

• Assuming greedy earliest end works for capacity constraints
• Thinking DP is needed for counting passengers
• Using brute force for large location ranges

2. Given two lists of closed intervals, each sorted and non-overlapping within themselves, you need to find all intervals where the two lists overlap. Which approach guarantees an optimal time complexity solution?

easy

A. Use a brute force nested loop to compare every interval in the first list with every interval in the second list.

B. Use two pointers to traverse both lists simultaneously, advancing the pointer with the smaller interval endpoint to find intersections efficiently.

C. Sort all intervals from both lists together and then merge overlapping intervals to find intersections.

D. Use dynamic programming to store and compute overlapping intervals between the two lists.

Solution

1. Step 1: Understand problem constraints

   Both lists are sorted and non-overlapping internally, so a linear scan is possible.

2. Step 2: Identify the optimal approach

   Two pointers allow simultaneous traversal, comparing intervals in O(m + n) time, advancing pointers based on interval endpoints.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Two pointers avoid unnecessary comparisons and achieve linear time [OK]

Hint: Two pointers exploit sorted order for linear time [OK]

Common Mistakes:

• Assuming brute force is acceptable
• Thinking sorting combined lists is needed
• Misapplying DP to interval intersection

3. Given a list of train arrival and departure times, you need to find the minimum number of platforms required so that no train waits. Which approach guarantees an optimal solution for this problem?

easy

A. Use a greedy algorithm that assigns platforms as trains arrive without sorting times.

B. Use a sweep line algorithm by creating events for arrivals and departures, sorting them, and tracking concurrent trains.

C. Use dynamic programming to find the maximum overlap of intervals by building a state table.

D. Use nested loops to check every pair of trains for overlap and count maximum overlaps.

Solution

1. Step 1: Understand the problem requires tracking concurrent trains

   The key is to find the maximum number of trains present at the station simultaneously.

2. Step 2: Recognize that sorting events and sweeping through them tracks concurrency efficiently

   By creating arrival and departure events and sorting them, we can increment or decrement the count of trains present, capturing the peak count.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sweep line tracks concurrency optimally [OK]

Hint: Sort events and sweep to track concurrency [OK]

Common Mistakes:

• Assuming greedy assignment without sorting works
• Trying DP which is unnecessary overhead
• Using nested loops which is inefficient

4. Consider the following Python function that returns the maximum number of non-overlapping intervals. What is the value of the variable removals after the second iteration of the loop when the input is [[1,3],[2,4],[3,5]]?

from typing import List

def max_non_overlapping_intervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: x[0])
    removals = 0
    last_end = intervals[0][1]
    for i in range(1, len(intervals)):
        if intervals[i][0] < last_end:
            removals += 1
            last_end = min(last_end, intervals[i][1])
        else:
            last_end = intervals[i][1]
    return len(intervals) - removals

intervals = [[1,3],[2,4],[3,5]]
print(max_non_overlapping_intervals(intervals))

easy

A. 1

B. 3

C. 2

D. 0

Solution

1. Step 1: Trace first iteration (i=1)

   Intervals sorted by start: [[1,3],[2,4],[3,5]]. last_end=3. At i=1, intervals[1][0]=2 < 3, so removals=1, last_end=min(3,4)=3.

2. Step 2: Trace second iteration (i=2)

   At i=2, intervals[2][0]=3 <= last_end=3 is false, so last_end=5, removals remains 1.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   removals incremented once at i=1 only [OK]

Hint: Check overlap condition carefully at each iteration [OK]

Common Mistakes:

• Off-by-one error in loop iteration
• Misunderstanding when to increment removals
• Confusing last_end update logic

5. Examine the following buggy code snippet for the minimum interval problem. Which line contains the subtle bug that can cause incorrect results on some inputs?

def min_interval_binary_search(intervals, queries):
    intervals.sort(key=lambda x: x[1] - x[0] + 1)
    lengths = [end - start for start, end in intervals]
    starts = [start for start, end in intervals]
    ends = [end for start, end in intervals]

    def covers(query, length):
        idx = bisect.bisect_right(lengths, length)
        for i in range(idx):
            if starts[i] <= query <= ends[i]:
                return True
        return False

    res = []
    max_len = lengths[-1] if lengths else 0
    for q in queries:
        left, right = 1, max_len
        ans = -1
        while left <= right:
            mid = (left + right) // 2
            if covers(q, mid):
                ans = mid
                right = mid - 1
            else:
                left = mid + 1
        res.append(ans)
    return res

medium

A. Line 15: max_len = lengths[-1] if lengths else 0

B. Line 2: intervals.sort(key=lambda x: x[1] - x[0] + 1)

C. Line 9: for i in range(idx):

D. Line 3: lengths = [end - start for start, end in intervals]

Solution

1. Step 1: Check interval length calculation

   Line 3 calculates lengths as end - start, missing the +1 needed for inclusive intervals.

2. Step 2: Impact of bug

   Incorrect lengths cause wrong sorting order and coverage checks, leading to wrong minimal interval lengths.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct interval length must be end - start + 1 [OK]

Hint: Check interval length calculation carefully [OK]

Common Mistakes:

• Off-by-one in length calculation
• Not sorting intervals
• Incorrect binary search boundaries