Meeting Rooms II (Minimum Conference Rooms)

📋

Problem

Imagine you are managing conference rooms in a busy office. You need to find the minimum number of rooms required so that all meetings can happen without overlap.

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required to hold all the meetings without conflicts.

1 ≤ n ≤ 10^50 ≤ start_i < end_i ≤ 10^9Intervals may overlap arbitrarily

Edge cases: All meetings are non-overlapping → output is 1All meetings overlap completely → output is nMeetings with same start and end times → count as overlapping

</>

IDE

def minMeetingRooms(intervals: list[list[int]]) -> int:public int minMeetingRooms(int[][] intervals)int minMeetingRooms(vector<vector<int>>& intervals)function minMeetingRooms(intervals)

def minMeetingRooms(intervals):
    # Write your solution here
    pass

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int minMeetingRooms(vector<vector<int>>& intervals) {
    // Write your solution here
    return 0;
}

function minMeetingRooms(intervals) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 1Treating meetings that end exactly when another starts as overlapping, causing undercounting of rooms.✅ Use strict comparison when checking overlaps: only count as overlap if start < end, not start <= end.

Wrong: 0Returning zero rooms for non-empty input or single meeting due to missing base case handling.✅ Add explicit checks to return 0 if intervals empty, and 1 if only one meeting.

Wrong: Less than actual rooms neededUsing a greedy approach that only considers earliest start times without tracking ongoing meetings' end times.✅ Use a min-heap to track earliest ending meeting and update room count dynamically.

Wrong: Less than actual rooms for identical intervalsMerging or ignoring identical intervals instead of treating each as separate meeting.✅ Push all intervals' end times into min-heap independently without merging.

Wrong: Timeout or no outputUsing brute force O(n^2) approach checking all pairs for overlap.✅ Sort intervals and use min-heap to achieve O(n log n) complexity.

✓

Test Cases

Focus on handling empty and minimal inputs correctly before tackling edge cases.

Review your approach for overlapping intervals and consider min-heap usage to avoid greedy traps.

Optimize your solution to O(n log n) by sorting and using a min-heap to handle large inputs efficiently.

t1_01basic

Input{"intervals":[[0,30],[5,10],[15,20]]}

Expected2

⏱ Performance - must finish in 2000ms

The first meeting overlaps with the second, so two rooms are needed. The third meeting starts after the second ends, so two rooms suffice.

💡 Consider sorting intervals by start time to process meetings chronologically.

💡 Use a min-heap to track the earliest ending meeting to reuse rooms efficiently.

💡 Push meeting end times into a min-heap and pop when a meeting ends before the next starts.

Why it failed: Returned fewer than 2 rooms, likely ignoring overlapping intervals or not tracking end times correctly. Fix by using a min-heap to track ongoing meetings and update room count accordingly.

✓ Correctly handles overlapping intervals and tracks minimum rooms needed.

t1_02basic

Input{"intervals":[[7,10],[2,4]]}

Expected1

⏱ Performance - must finish in 2000ms

Meetings do not overlap; only one room is needed.

💡 Check if meetings overlap by comparing start time of current with earliest end time of ongoing meetings.

💡 If no overlap, reuse the same room by removing ended meetings from the min-heap.

💡 Ensure to pop from min-heap when the earliest meeting ends before the next starts.

Why it failed: Returned more than 1 room despite no overlaps; likely not removing ended meetings from min-heap. Fix by popping from min-heap when current meeting starts after earliest end time.

✓ Correctly identifies no overlaps and returns one room.

t2_01edge

Input{"intervals":[]}

Expected0

⏱ Performance - must finish in 2000ms

No meetings means no rooms needed.

💡 Consider the case when input list is empty.

💡 Return 0 immediately if there are no intervals.

💡 Check for empty input before processing to avoid errors.

Why it failed: Returned non-zero for empty input; fix by adding a check to return 0 if intervals list is empty.

✓ Correctly returns 0 rooms for empty input.

t2_02edge

Input{"intervals":[[1,2]]}

Expected1

⏱ Performance - must finish in 2000ms

Single meeting requires only one room.

💡 Check behavior with only one interval.

💡 Minimum rooms for one meeting is always one.

💡 Ensure code handles single element without errors.

Why it failed: Returned 0 or more than 1 for single meeting; fix by returning 1 if intervals length is 1.

✓ Correctly returns 1 room for single meeting.

t2_03edge

Input{"intervals":[[1,5],[5,10],[10,15]]}

Expected1

⏱ Performance - must finish in 2000ms

Meetings end exactly when the next starts; no overlap, so one room suffices.

💡 Check if meetings that end exactly when another starts count as overlapping.

💡 Meetings with end time equal to next start time do not overlap.

💡 Use strict less than (<) when comparing start and end times to avoid counting these as overlaps.

Why it failed: Returned more than 1 room due to treating end == start as overlap; fix by using strict comparison (start < end) for overlap detection.

✓ Correctly treats meetings ending at start time of next as non-overlapping.

t3_01corner

Input{"intervals":[[1,10],[2,7],[3,19],[8,12],[10,20],[11,30]]}

Expected4

⏱ Performance - must finish in 2000ms

Multiple overlapping intervals requiring careful tracking of rooms; greedy approach picking earliest start only fails here.

💡 Beware of greedy approaches that only consider earliest start times.

💡 Use a min-heap to track earliest end times to reuse rooms optimally.

💡 Update room count by popping all meetings that ended before current starts.

Why it failed: Returned fewer than 4 rooms due to greedy approach ignoring ongoing overlaps; fix by using min-heap to track end times and update room count dynamically.

✓ Correctly handles complex overlapping intervals with min-heap.

t3_02corner

Input{"intervals":[[1,5],[1,5],[1,5],[1,5]]}

Expected4

⏱ Performance - must finish in 2000ms

All meetings overlap completely; number of rooms equals number of meetings.

💡 Check if your code handles multiple identical intervals correctly.

💡 Each identical interval requires a separate room since they overlap fully.

💡 Ensure min-heap does not merge or ignore identical intervals.

Why it failed: Returned fewer than 4 rooms by incorrectly merging identical intervals; fix by treating each interval independently and pushing all end times into min-heap.

✓ Correctly counts rooms for fully overlapping identical intervals.

t3_03corner

Input{"intervals":[[0,5],[5,10],[5,15],[10,20]]}

Expected2

⏱ Performance - must finish in 2000ms

Meetings starting exactly when others end; tests strict inequality and heap update correctness.

💡 Verify that meetings starting at the exact end time of others do not increase room count.

💡 Pop from min-heap all meetings that ended before or at current start time.

💡 Use <= comparison when popping from min-heap to free rooms.

Why it failed: Returned more than 2 rooms by treating end == start as overlap; fix by popping from min-heap when earliest end time <= current start time.

✓ Correctly handles meetings starting at end time of others.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 intervals with arbitrary overlaps; O(n log n) sorting and heap operations must complete within 2 seconds.

💡 Sorting intervals by start time is essential for efficiency.

💡 Use a min-heap to track end times and achieve O(n log n) complexity.

💡 Avoid brute force O(n^2) overlap checks which will time out.

Why it failed: Solution timed out due to O(n^2) brute force approach; fix by sorting intervals and using a min-heap to track ongoing meetings for O(n log n) complexity.

✓ Efficient O(n log n) solution confirmed by passing performance test.

Practice

1. 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

2. What is the time complexity of the optimal in-place merge intervals algorithm that first sorts the intervals and then merges them in one pass?

medium

A. O(n log n) due to the sorting step dominating the runtime

B. O(n) because merging is done in a single pass

C. O(n²) because each interval is compared with all others during merging

D. O(n log n) because merging requires binary searches for overlaps

Solution

1. Step 1: Identify the sorting step complexity.

   Sorting n intervals by start time takes O(n log n) time.

2. Step 2: Analyze the merging step complexity.

   Merging intervals in one pass is O(n), which is dominated by sorting.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates overall complexity, merging is linear. [OK]

Hint: Sorting dominates, merging is linear [OK]

Common Mistakes:

• Ignoring sorting cost
• Assuming nested comparisons cause O(n²)

3. The following code attempts to find the minimum number of arrows to burst balloons. Identify the bug that causes incorrect arrow count in some cases.

medium

A. Line 6: Shooting arrow at start coordinate instead of end coordinate

B. Line 4: Sorting by end coordinate is incorrect

C. Line 2: Missing check for empty input

D. Line 8: Using start > arrow_pos instead of start >= arrow_pos

Solution

1. Step 1: Analyze arrow shooting position

   Arrow should be shot at the end coordinate of the first balloon to cover maximum overlaps.

2. Step 2: Identify impact of shooting at start

   Shooting at start may miss balloons overlapping at the end, causing extra arrows.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct arrow position is critical for minimal arrow count [OK]

Hint: Arrow must be at end coordinate, not start [OK]

Common Mistakes:

• Confusing start and end coordinates for arrow position
• Using >= instead of > causing overcount
• Ignoring empty input edge case

4. If employees can have intervals with negative start or end times (e.g., [-5, 0]) or zero-length intervals, which modification to the sweep line algorithm is necessary to correctly find free time?

hard

A. Ignore zero-length intervals and ensure sorting places end events before start events at ties

B. Treat zero-length intervals as free time intervals

C. Sort events only by time, ignoring event type

D. Merge touching intervals as free time gaps

Solution

1. Step 1: Handle zero-length intervals

   Zero-length intervals like [2,2] do not represent busy time and should be ignored to avoid false free intervals.

2. Step 2: Maintain correct sorting order

   Sorting end events before start events at same time prevents reporting free time between touching intervals or zero-length intervals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Ignoring zero-length intervals and correct sorting avoids invalid free times [OK]

Hint: Ignore zero-length intervals and sort end before start events [OK]

Common Mistakes:

• Counting zero-length intervals as free time
• Sorting start before end events

5. Suppose trains can arrive and depart multiple times (reusing platforms) and the schedule may include negative time values (e.g., early morning times). Which modification to the sweep line algorithm ensures correct minimum platform calculation?

hard

A. Use the same sweep line approach but ensure sorting handles negative times correctly and process events with departure before arrival on tie.

B. Use dynamic programming to handle multiple arrivals and departures per train.

C. Switch to nested loops checking overlaps since negative times break sorting assumptions.

D. Ignore negative times and treat them as zero to simplify sorting.

Solution

1. Step 1: Recognize that negative times do not affect event sorting if handled correctly

   Sorting supports negative values naturally; no need to ignore or clamp them.

2. Step 2: Maintain departure-before-arrival ordering on tie to avoid overcounting

   This ordering is critical regardless of time values or multiple arrivals/departures.

3. Step 3: Continue using sweep line approach for efficiency and correctness

   Nested loops or DP are inefficient or unnecessary for this variant.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sweep line with correct sorting handles negative and multiple events [OK]

Hint: Sorting handles negative times; keep departure before arrival on tie [OK]

Common Mistakes:

• Ignoring negative times or clamping them
• Switching to inefficient nested loops unnecessarily
• Misordering events causing overcounting