Meeting Rooms I

📋

Problem

Imagine you have a conference room and a list of meetings scheduled with start and end times. You want to know if you can hold all meetings in that single room without any overlaps.

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings without any overlaps. Return true if no meetings overlap, otherwise false.

1 ≤ n ≤ 10^50 ≤ start_i < end_i ≤ 10^9Intervals may not be sorted initially

Edge cases: Single meeting → always trueMeetings that touch but do not overlap, e.g. [1,5] and [5,10] → trueMeetings with same start and end times, e.g. [2,2] → true (zero length meeting)

</>

IDE

def can_attend_meetings(intervals: list[list[int]]) -> bool:public boolean canAttendMeetings(int[][] intervals)bool canAttendMeetings(vector<vector<int>>& intervals)function canAttendMeetings(intervals)

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

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool canAttendMeetings(vector<vector<int>>& intervals) {
    // Write your solution here
    return false;
}

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

Common Bugs to Avoid

Wrong: trueFailing to detect overlapping intervals due to missing sorting or incorrect overlap condition.✅ Sort intervals by start time and check if intervals[i][0] < intervals[i-1][1] to detect overlaps.

Wrong: falseIncorrectly treating touching intervals as overlapping by using <= instead of < in overlap check.✅ Use strict less-than comparison intervals[i][0] < intervals[i-1][1] to allow touching intervals.

Wrong: falseFailing on empty or single interval inputs by not handling these base cases explicitly.✅ Return true immediately if intervals list is empty or has only one interval.

Wrong: trueUsing a greedy approach that only checks earliest start without verifying all overlaps.✅ Sort intervals and check all adjacent pairs for overlaps, not just earliest start.

Wrong: TLEUsing nested loops (O(n^2)) for overlap detection on large inputs.✅ Use sorting plus single pass overlap check to achieve O(n log n) time complexity.

✓

Test Cases

Try testing your solution on empty and single meeting inputs to ensure base cases are handled.

Consider tricky cases with nested or zero-length intervals to catch subtle bugs.

Optimize your solution to avoid nested loops; sorting plus single pass is key.

t1_01basic

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

Expectedfalse

⏱ Performance - must finish in 2000ms

The meeting [0,30] overlaps with [5,10], so it's impossible to attend all.

💡 Sort intervals by start time and check for overlaps between consecutive intervals.

💡 If any interval's start is less than the previous interval's end, return false.

💡 Return false immediately when overlap found; otherwise true after checking all.

Why it failed: Returned true despite overlapping intervals. Fix by sorting intervals and checking if intervals[i][0] < intervals[i-1][1].

✓ Correctly detected overlapping intervals and returned false.

t1_02basic

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

Expectedtrue

⏱ Performance - must finish in 2000ms

No meetings overlap; intervals [2,4] and [7,10] are separate.

💡 Sort intervals by start time to compare adjacent intervals easily.

💡 Check if any interval starts before the previous one ends.

💡 Since no overlaps found, return true.

Why it failed: Returned false incorrectly; likely failed to sort intervals before overlap check.

✓ Correctly identified no overlaps and returned true.

t2_01edge

Input{"intervals":[]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty list means no meetings, so trivially no overlaps.

💡 Consider the case when intervals list is empty.

💡 No meetings means no conflicts, so return true immediately.

💡 Check if length of intervals is zero and return true.

Why it failed: Returned false or error on empty input. Fix by returning true if intervals is empty.

✓ Correctly handled empty input by returning true.

t2_02edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Single meeting cannot overlap with anything else.

💡 Check behavior when only one meeting is present.

💡 Single interval means no overlap possible.

💡 Return true if intervals length is 1.

Why it failed: Returned false incorrectly for single interval. Fix by returning true if intervals length <= 1.

✓ Correctly returned true for single meeting.

t2_03edge

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Meetings that touch but do not overlap are allowed.

💡 Check if intervals that end exactly when next starts are considered overlapping.

💡 Overlap occurs only if start < previous end, not <=.

💡 Use strict less-than comparison for overlap detection.

Why it failed: Returned false incorrectly for touching intervals. Fix by using intervals[i][0] < intervals[i-1][1] for overlap check, not <=.

✓ Correctly allowed meetings that touch but do not overlap.

t3_01corner

Input{"intervals":[[1,10],[2,3],[4,5],[6,7]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Nested intervals cause overlap; greedy approach picking earliest start only fails.

💡 Sorting only by start time is not enough; check all adjacent intervals after sorting.

💡 A greedy approach picking earliest start without checking overlaps fails here.

💡 Sort intervals by start and check if intervals[i][0] < intervals[i-1][1] to detect overlap.

Why it failed: Returned true incorrectly due to greedy approach ignoring nested overlaps. Fix by sorting and checking all adjacent intervals for overlap.

✓ Correctly detected nested overlaps and returned false.

t3_02corner

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

Expectedtrue

⏱ Performance - must finish in 2000ms

Zero-length meetings at same time do not overlap.

💡 Check how zero-length intervals are handled.

💡 Overlap requires intervals[i][0] < intervals[i-1][1], zero-length means start == end.

💡 Ensure strict less-than comparison to allow zero-length intervals at same time.

Why it failed: Returned false incorrectly for zero-length intervals. Fix by using strict less-than comparison for overlap detection.

✓ Correctly handled zero-length intervals as non-overlapping.

t3_03corner

Input{"intervals":[[1,4],[2,5],[5,6]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Overlap between [1,4] and [2,5] causes false; test catches off-by-one errors.

💡 Check if your code correctly detects overlaps when intervals partially overlap.

💡 Overlap occurs if intervals[i][0] < intervals[i-1][1], not <=.

💡 Fix off-by-one errors by using strict less-than comparison.

Why it failed: Returned true incorrectly due to off-by-one error in overlap check. Fix by using intervals[i][0] < intervals[i-1][1].

✓ Correctly detected partial overlaps and returned false.

t4_01performance

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

Expectednull

⏱ Performance - must finish in 2000ms

n=100000 intervals must be processed in O(n log n) time within 2 seconds.

💡 Sorting intervals is O(n log n), which is efficient for n=100000.

💡 Avoid nested loops; use single pass after sorting to check overlaps.

💡 Use efficient sorting and early exit on overlap detection.

Why it failed: TLE due to O(n^2) nested loops approach. Fix by sorting intervals and checking overlaps in a single pass (O(n log n)).

✓ Algorithm runs in O(n log n) time and passes performance test.

Practice

1. Given multiple employees' schedules with intervals representing their busy times, which algorithmic approach guarantees finding all common free time intervals where no employee is busy?

easy

A. Greedy interval scheduling that picks earliest finishing intervals

B. Dynamic programming to find maximum non-overlapping intervals

C. Sweep line / event processing that tracks interval start and end events

D. Brute force checking every time point across all intervals

Solution

1. Step 1: Understand problem requires identifying gaps where no intervals overlap

   Greedy scheduling or DP focus on selecting intervals, not gaps between them.

2. Step 2: Sweep line processes all start/end events in order, tracking active intervals to find free gaps

   This approach efficiently detects when no employee is busy, yielding correct free times.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sweep line tracks active intervals and finds free gaps [OK]

Hint: Sweep line tracks interval endpoints to find free gaps [OK]

Common Mistakes:

• Assuming greedy or DP can find free gaps directly

2. Consider the following Python function that finds the minimum number of arrows to burst balloons represented as intervals. Given the input points = [[10,16],[2,8],[1,6],[7,12]], what is the value of arrows after processing all intervals?

easy

A. 1

B. 4

C. 3

D. 2

Solution

1. Step 1: Sort intervals by end coordinate

   Sorted points: [[1,6],[2,8],[7,12],[10,16]]

2. Step 2: Iterate and count arrows

   Start with arrow_pos=6, arrows=1. Next interval start=2 ≤ 6 (covered), next start=7 > 6 (new arrow), arrows=2, arrow_pos=12. Next start=10 ≤ 12 (covered).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two arrows suffice to burst all balloons [OK]

Hint: Sort by end, count arrows when start > current arrow position [OK]

Common Mistakes:

• Not sorting intervals before processing
• Using start >= arrow_pos instead of start > arrow_pos
• Off-by-one errors in counting arrows

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 greedy algorithm that finds the maximum number of non-overlapping intervals by sorting intervals and iterating through them once?

medium

A. O(n log n) due to sorting plus O(n) iteration, total O(n log n)

B. O(n^2) due to nested comparisons between intervals

C. O(n) since it only iterates once through the intervals

D. O(n log n) because of sorting intervals by start or end time

Solution

1. Step 1: Identify sorting cost

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

2. Step 2: Identify iteration cost

   Iterating through the sorted intervals to select non-overlapping ones takes O(n) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting dominates, total complexity is O(n log n) [OK]

Hint: Sorting dominates time complexity in interval scheduling [OK]

Common Mistakes:

• Assuming iteration alone is O(n) and ignoring sorting
• Mistaking nested loops causing O(n^2)
• Confusing sorting and iteration costs

5. Suppose the car pooling problem is modified so that trips can overlap and passengers can be picked up and dropped off multiple times (i.e., trips can reuse the same passengers). Which of the following algorithmic changes correctly adapts the solution to handle this variant efficiently?

hard

A. Use a segment tree or binary indexed tree to efficiently update and query passenger counts over intervals

B. Switch to a priority queue to process events in order and track current passengers dynamically

C. Use the same difference array approach but multiply passenger counts by the number of trips to simulate reuse

D. Modify the difference array to allow negative passenger counts and track net changes carefully

Solution

1. Step 1: Understand reuse complexity

   Reusing passengers means overlapping intervals can increase and decrease counts multiple times, requiring efficient range updates and queries.

2. Step 2: Identify suitable data structure

   Segment trees or binary indexed trees support efficient interval updates and queries, handling overlapping intervals with reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Segment trees handle dynamic interval sums efficiently [OK]

Hint: Reuse -> need data structure for interval updates [OK]

Common Mistakes:

• Multiplying counts breaks logic
• Priority queue alone can't handle reuse efficiently
• Allowing negative counts without structure causes errors