Bird
Raised Fist0
Interview PrepintervalsmediumFacebookAmazonBloombergGoogle

Meeting Rooms II (Minimum Conference Rooms)

Choose your preparation mode4 modes available
📋
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
}
0/9
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
t1_01basic
Input{"intervals":[[0,30],[5,10],[15,20]]}
Expected2

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

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

Meetings do not overlap; only one room is needed.

t2_01edge
Input{"intervals":[]}
Expected0

No meetings means no rooms needed.

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

Single meeting requires only one room.

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

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

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

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

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

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

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

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

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

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

Practice

(1/5)
1. You are given a list of time intervals representing booked meeting rooms. Your task is to combine all overlapping intervals into the minimum number of non-overlapping intervals. Which algorithmic approach guarantees an optimal and efficient solution for this problem?
easy
A. Use a greedy approach that always merges the earliest starting interval with the next one without sorting.
B. Sort intervals by start time and then merge overlapping intervals in a single pass.
C. Use dynamic programming to find the maximum number of non-overlapping intervals and then merge accordingly.
D. Check every pair of intervals with nested loops to merge overlaps until no overlaps remain.

Solution

  1. Step 1: Understand the problem requires merging overlapping intervals efficiently.

    Sorting intervals by their start time ensures that overlapping intervals are adjacent, enabling a single pass merge.
  2. Step 2: Evaluate each option's approach.

    Use a greedy approach that always merges the earliest starting interval with the next one without sorting. fails because without sorting, intervals may be merged incorrectly or missed. Use dynamic programming to find the maximum number of non-overlapping intervals and then merge accordingly. is unrelated as DP is not needed here. Check every pair of intervals with nested loops to merge overlaps until no overlaps remain. is brute force with O(n²) time, inefficient for large inputs. Sort intervals by start time and then merge overlapping intervals in a single pass. correctly sorts and merges in O(n log n) time.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sorting + one pass merge is the classic optimal pattern for merging intervals. [OK]
Hint: Sort intervals first, then merge in one pass [OK]
Common Mistakes:
  • Trying to merge without sorting
  • Using nested loops leading to O(n²) time
2. Given the following code and input intervals = [[1,4],[3,6],[2,8]], what is the value of count after the loop finishes?
easy
A. 2
B. 1
C. 3
D. 0

Solution

  1. Step 1: Sort intervals by start ascending, end descending

    Sorted intervals: [[1,4],[2,8],[3,6]]
  2. Step 2: Iterate and update count and max_end

    Iteration 1: end=4 > max_end=0 -> count=1, max_end=4 Iteration 2: end=8 > max_end=4 -> count=2, max_end=8 Iteration 3: end=6 ≤ max_end=8 -> count unchanged
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Count increments twice for uncovered intervals [OK]
Hint: Sort then count intervals with strictly greater end [OK]
Common Mistakes:
  • Misorder intervals after sorting
  • Off-by-one counting in loop
3. What is the time complexity of the optimal car pooling solution using the difference array and prefix sum approach, given n trips and maximum location L?
medium
A. O(n * L) because we must simulate passenger count at every location for each trip
B. O(n + L) because we process each trip once and then sweep through the difference array once
C. O(n log n) due to sorting trips by start location before processing
D. O(L) because the difference array size dominates and trips are processed in constant time

Solution

  1. Step 1: Analyze trip processing

    Each of the n trips updates two positions in the difference array -> O(n)
  2. Step 2: Analyze prefix sum sweep

    We iterate over the difference array of size L once -> O(L)
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Sum of O(n) + O(L) operations [OK]
Hint: Difference array updates O(n), prefix sum O(L) [OK]
Common Mistakes:
  • Confusing brute force O(n*L) with optimal
  • Assuming sorting is required
  • Ignoring prefix sum sweep cost
4. What is the time complexity of the addNum operation in the optimal balanced tree approach for maintaining disjoint intervals, assuming there are n intervals stored?
medium
A. O(n) because intervals need to be scanned linearly for merging
B. O(log n) due to binary search and limited merging operations
C. O(n log n) because each insertion requires sorting intervals
D. O(1) since insertion is always at the end or start

Solution

  1. Step 1: Identify main operations in addNum

    addNum uses binary search (bisect_left) to find insertion index in O(log n).
  2. Step 2: Analyze merging cost

    Merging involves at most constant number of interval merges (left, right, or both), so O(1) extra work.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Binary search dominates, merges are constant time [OK]
Hint: Binary search + constant merges -> O(log n) [OK]
Common Mistakes:
  • Assuming linear scan for merging
  • Confusing sorting cost per insertion
  • Ignoring constant merge steps
5. Suppose intervals can be reused multiple times (i.e., you can select the same interval multiple times if it does not overlap with itself). Which modification to the greedy algorithm is correct to find the maximum number of non-overlapping intervals under this new condition?
hard
A. Sort intervals by end time and greedily select intervals, resetting last_end after each selection to allow reuse.
B. Use dynamic programming to consider multiple selections of intervals, since greedy no longer works.
C. Sort intervals by start time and greedily select intervals without updating last_end to allow reuse.
D. Sort intervals by end time and greedily select intervals, but allow intervals to be selected multiple times by not updating last_end.

Solution

  1. Step 1: Understand reuse changes problem

    Allowing reuse means intervals can be selected multiple times, breaking the greedy assumption of one-time selection.
  2. Step 2: Identify correct approach

    Dynamic programming is needed to explore multiple selections and ensure maximum count without overlap.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Greedy fails with reuse; DP handles multiple selections [OK]
Hint: Reuse breaks greedy; DP needed for multiple selections [OK]
Common Mistakes:
  • Trying to reuse intervals by resetting last_end incorrectly
  • Ignoring overlap constraints when reusing intervals
  • Assuming greedy still works unchanged
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard