Bird
Raised Fist0
Interview PrepintervalseasyFacebookAmazonBloomberg

Meeting Rooms I

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

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

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

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

t2_01edge
Input{"intervals":[]}
Expectedtrue

Empty list means no meetings, so trivially no overlaps.

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

Single meeting cannot overlap with anything else.

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

Meetings that touch but do not overlap are allowed.

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

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

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

Zero-length meetings at same time do not overlap.

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

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

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

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

Practice

(1/5)
1. Consider the following Python code that merges intervals in-place after sorting. Given the input intervals = [[1,4],[2,5],[7,9]], what is the returned list after the function completes?
easy
A. [[1,5],[7,9]]
B. [[1,4],[2,5],[7,9]]
C. [[1,5],[2,5],[7,9]]
D. [[1,4],[7,9]]

Solution

  1. Step 1: Sort intervals by start time.

    Input is already sorted: [[1,4],[2,5],[7,9]].
  2. Step 2: Merge intervals in one pass.

    Compare [2,5] with [1,4]: overlap since 2 <= 4, merge to [1,5]. Then compare [7,9] with [1,5]: no overlap, move index forward and assign [7,9]. Final intervals: [[1,5],[7,9]].
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Overlapping intervals merged correctly, non-overlapping preserved. [OK]
Hint: Check if current start ≤ last merged end to merge [OK]
Common Mistakes:
  • Returning original intervals without merging
  • Off-by-one slicing errors
2. 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
3. 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
4. Examine the following buggy code for interval intersections:
def intervalIntersection(A, B):
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] <= B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result
What is the bug in this code?
medium
A. The condition 'if A[i][1] <= B[j][0]' should use '<' instead of '<=' to correctly detect touching intervals.
B. The pointer increments inside the else block are reversed; they should increment the pointer with the larger endpoint.
C. The overlap condition should check 'start < end' instead of 'start <= end' to avoid zero-length intervals.
D. The code does not handle empty input lists, which can cause runtime errors.

Solution

  1. Step 1: Analyze overlap condition

    Using '<=' excludes intervals that touch at a point (e.g., end == start), missing valid intersections.
  2. Step 2: Correct condition

    Changing to '<' ensures intervals that share a boundary point are considered intersecting.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Inclusive endpoints require '<' not '<=' to detect touching intervals [OK]
Hint: Check boundary conditions carefully for inclusive intervals [OK]
Common Mistakes:
  • Using <= instead of <
  • Reversing pointer increments
  • Ignoring empty inputs
5. The following code attempts to merge intervals in-place after sorting. Identify the line that contains a subtle bug causing incorrect results on some inputs.
medium
A. Line 3: intervals.sort(key=lambda x: x[0])
B. Line 9: intervals[index][1] = max(intervals[index][1], intervals[i][1])
C. Line 12: return intervals # missing slicing after in-place merge
D. Line 8: if intervals[i][0] <= intervals[index][1]:

Solution

  1. Step 1: Understand the in-place merge modifies intervals up to index.

    After merging, only intervals[:index+1] are valid merged intervals.
  2. Step 2: Identify the bug in the return statement.

    Returning the entire intervals list without slicing includes extra unmerged intervals, causing incorrect output.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Return intervals[:index+1] to exclude leftover intervals. [OK]
Hint: Return sliced intervals after in-place merge [OK]
Common Mistakes:
  • Forgetting to slice after in-place merge
  • Modifying list while iterating without adjusting index
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