Meeting Rooms I

▶

Steps

setup

Start with the input intervals

The algorithm receives the input array of intervals: [[0,30],[5,10],[15,20]].

💡 Knowing the initial unsorted intervals helps understand why sorting is necessary.

Line:

def can_attend_meetings(intervals: List[List[int]]) -> bool:

💡 The input intervals are unordered and may overlap.

setup

Sort intervals by start time

The intervals array is sorted by the start time of each meeting.

💡 Sorting ensures we check meetings in chronological order, which is key to detecting overlaps efficiently.

Line:

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

💡 Sorting arranges intervals so that any overlap will be between consecutive intervals.

setup

Initialize end time tracker

Set the variable 'end' to negative infinity to represent no meetings have been processed yet.

💡 This variable will track the end time of the last meeting to detect overlaps.

Line:

end = float('-inf')

💡 Starting with -inf ensures the first meeting will always be considered non-overlapping.

traverse

Start iterating over intervals

Set pointer 'i' to the first interval at index 0 to begin checking for overlaps.

💡 We will check each interval in order to detect any conflicts.

Line:

for interval in intervals:

💡 Iteration allows sequential comparison of intervals.

compare

Compare start time with tracked end time

Check if the start time of the current interval (0) is less than 'end' (-inf).

💡 This comparison detects if the current meeting overlaps with the previous one.

Line:

if interval[0] < end:

💡 The first meeting cannot overlap since 'end' is -inf.

insert

Update end time to current interval's end

Since no overlap was found, update 'end' to the end time of the current interval, 30.

💡 Tracking the latest meeting's end time is essential for future overlap checks.

Line:

end = interval[1]

💡 The end time now reflects the last meeting's finish time.

traverse

Move to next interval

Increment pointer 'i' to index 1 to check the next interval [5,10].

💡 Each interval must be checked to ensure no overlaps exist.

Line:

for interval in intervals:

💡 Sequential checking is necessary for correctness.

compare

Compare start time with tracked end time

Check if the start time of the current interval (5) is less than 'end' (30).

💡 This comparison detects if the current meeting overlaps with the previous one.

Line:

if interval[0] < end:

💡 The current meeting starts before the last one ends, so they overlap.

prune

Return false due to overlap

Since an overlap is detected, the function returns false immediately, indicating not all meetings can be attended.

💡 Early exit saves time by stopping further unnecessary checks.

Line:

return False

💡 The algorithm efficiently detects conflicts and stops early.

final

Final result: cannot attend all meetings

The algorithm concludes that attending all meetings is impossible due to overlapping intervals.

💡 This final state confirms the algorithm's decision based on the input.

Line:

return True  # not reached in this input

💡 The presence of any overlap means the answer is false.

from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])  # STEP 2: sort intervals by start time
    end = float('-inf')  # STEP 3: initialize end time tracker
    for interval in intervals:  # STEP 4: iterate over intervals
        if interval[0] < end:  # STEP 5 & 8: check for overlap
            return False  # STEP 9: early exit on overlap
        end = interval[1]  # STEP 6: update end time
    return True  # STEP 10: no overlaps found

📊

Meeting Rooms I - Watch the Algorithm Execute, Step by Step

Watching each comparison and pointer movement helps you understand how the algorithm detects overlaps early and why sorting by start time is crucial.

none

0

1

2

sort

0

1

2

initialize

0

1

2

traverse

i

0

1

2

compare

i

0

1

2

insert

i

0

1

2

traverse

0

i

1

2

compare

0

i

1

2

Result: false

prune

0

i

1

2

Result: false

final

0

i

1

2

Result: false

Key Takeaways

✓ Sorting intervals by start time is essential to detect overlaps efficiently.

Without sorting, overlaps could be missed or require more complex checks.

✓ Tracking the end time of the last meeting allows quick overlap detection with the next meeting.

This insight shows how a single variable can summarize past intervals for efficient comparison.

✓ Early exit on detecting an overlap saves computation and immediately gives the answer.

This optimization is hard to see in code alone but is clear when watching the algorithm stop mid-iteration.

Practice

1. Consider the following Python function implementing the line sweep algorithm to count intervals containing each point. Given intervals = [[1,4],[2,5],[7,9]] and points = [2,5,8], what is the final output of the function call count_intervals_line_sweep(intervals, points)?

easy

A. [2, 1, 1]

B. [2, 1, 0]

C. [1, 2, 1]

D. [2, 2, 1]

Solution

1. Step 1: Sort events and process starts

   Events: (1,+1), (2,+1), (2,0), (5,0), (5+1,-1), (4+1,-1), (7,+1), (8,0), (9+1,-1). Sorted order processes starts before points, points before ends.

2. Step 2: Track active intervals and assign counts at points

   At point 2: active=2 (intervals [1,4],[2,5]), at point 5: active=1 (only [2,5] ends at 6), at point 8: active=0 (interval [7,9] ended at 10, but 8 < 10 so active=1 actually, re-check)

3. Correction Step 2:

   At point 8: interval [7,9] is active, so active=1. So final counts: [2,1,1]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting active intervals at each point matches expected output [OK]

Hint: Remember to add 1 to interval ends for event ordering [OK]

Common Mistakes:

• Forgetting end+1 shifts interval end
• Misordering events causing wrong active count
• Off-by-one in active count at points

2. Consider the following Python code implementing the min-heap approach to find the minimum number of meeting rooms. Given the input intervals = [[0,30],[5,10],[15,20]], what is the value of the heap after processing the second interval (i=1)?

easy

A. [10]

B. [30, 10]

C. [30, 20]

D. [5, 10]

Solution

1. Step 1: Trace heap after first interval [0,30].

   Heap contains [30] after pushing end time of first meeting.

2. Step 2: Process second interval [5,10].

   Since 5 < 30 (heap[0]), no pop occurs; push 10. Heap now contains [10, 30] (min-heap property).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap stores end times; after second interval, both 30 and 10 are in heap [OK]

Hint: Heap stores end times; no pop if start < earliest end [OK]

Common Mistakes:

• Popping when start < earliest end
• Confusing heap contents order
• Forgetting to push current interval's end

3. What is the time complexity of the optimal approach that inserts a new interval into a list of n intervals and merges overlapping intervals, where the approach is to append the new interval, sort all intervals by start time, then merge in one pass?

medium

A. O(n)

B. O(n^2)

C. O(n log n)

D. O(log n)

Solution

1. Step 1: Identify sorting cost

   Appending is O(1), but sorting n+1 intervals takes O(n log n) time.

2. Step 2: Identify merging cost

   Merging intervals in one pass is O(n) since each interval is processed once.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting dominates overall time complexity [OK]

Hint: Sorting dominates time complexity -> O(n log n) [OK]

Common Mistakes:

• Assuming linear time because merging is O(n)
• Confusing sorting cost with merging cost
• Thinking recursion stack adds extra complexity

4. What is the time complexity of the optimal min-heap approach for the Meeting Rooms II problem, given n intervals? Beware of common misconceptions about sorting and heap operations.

medium

A. O(n log k) where k is the number of rooms, but k can be up to n, so effectively O(n log n).

B. O(n^2) because each interval may be compared with all others.

C. O(n log n) due to sorting and heap operations for each interval.

D. O(n) because heap operations are constant time on average.

Solution

1. Step 1: Identify sorting cost.

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

2. Step 2: Analyze heap operations.

   Each interval is pushed and possibly popped from a min-heap of size k (number of rooms). Each heap operation costs O(log k).

3. Step 3: Combine complexities.

   Total heap operations are O(n log k). Since k ≤ n, worst case is O(n log n).

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Sorting + heap operations dominate; heap size bounded by n [OK]

Hint: Heap ops depend on number of rooms k, bounded by n [OK]

Common Mistakes:

• Assuming heap ops are O(1)
• Confusing n and k in complexity
• Thinking sorting is O(n)

5. Suppose meetings can be scheduled with negative start or end times (e.g., representing times before a reference point). Which modification to the min-heap approach is necessary to correctly compute the minimum number of meeting rooms?

hard

A. Adjust the comparison in the heap to handle negative end times by using a max-heap instead of min-heap.

B. Sort intervals by absolute value of start times to handle negative values correctly.

C. Sort intervals normally by start time and use the min-heap approach as usual; negative times do not affect logic.

D. No modification needed; the existing min-heap approach works regardless of negative times.

Solution

1. Step 1: Understand sorting by start time works with negative values.

   Sorting by start time orders intervals correctly even if times are negative.

2. Step 2: Confirm min-heap logic remains valid.

   Heap tracks earliest end time; negative values do not affect min-heap property or comparison logic.

3. Step 3: No need for absolute value sorting or max-heap.

   Using absolute values or max-heap breaks the logic of interval ordering and room reuse.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Negative times do not change sorting or heap logic [OK]

Hint: Sorting by start time works even with negative times [OK]

Common Mistakes:

• Sorting by absolute values breaks interval order
• Switching to max-heap unnecessarily
• Assuming negative times require special handling