Bird
Raised Fist0
Interview PrepintervalseasyFacebookAmazonBloomberg

Meeting Rooms I

Choose your preparation mode4 modes available
🎯
Meeting Rooms I
easyINTERVALSFacebookAmazonBloomberg

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.

💡 This problem is about checking if any intervals overlap. Beginners often struggle because they don't realize that sorting intervals by start time simplifies the overlap check. Without sorting, it's hard to efficiently detect conflicts.
📋
Problem Statement

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
💡
Example
Input"[[0,30],[5,10],[15,20]]"
Outputfalse

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

Input"[[7,10],[2,4]]"
Outputtrue

No meetings overlap, so all can be attended.

  • Single meeting → always true
  • Meetings that touch but do not overlap, e.g. [1,5] and [5,10] → true
  • Meetings with same start and end times, e.g. [2,2] → true (zero length meeting)
  • Large number of meetings with no overlaps → true
⚠️
Common Mistakes
Not sorting intervals before checking overlaps

Missed overlaps between non-adjacent intervals, leading to incorrect true result

✅ Always sort intervals by start time before checking overlaps

Using <= instead of < in overlap condition

Incorrectly detects overlap when meetings just touch (e.g., [1,5] and [5,10])

✅ Use strict less than (<) to allow meetings that end exactly when another starts

Not handling empty or single interval input

Code may crash or return wrong result

✅ Check for empty or single interval cases and return true immediately

Confusing start and end indices in intervals

Wrong comparisons leading to false positives or negatives

✅ Be consistent: intervals[i][0] is start, intervals[i][1] is end

Not returning immediately after detecting overlap

Unnecessary computations wasting time

✅ Return false as soon as overlap is found

🧠
Brute Force (Nested Loops Overlap Check)
💡 This approach exists to build intuition by directly checking every pair of meetings for overlap. It’s simple but inefficient, showing why optimization is needed.

Intuition

Check every pair of intervals to see if they overlap. If any pair overlaps, return false; otherwise, true.

Algorithm

  1. For each meeting, compare it with every other meeting.
  2. Check if the two meetings overlap by comparing their start and end times.
  3. If any overlap is found, return false immediately.
  4. If no overlaps are found after all comparisons, return true.
💡 The nested loops make it easy to understand the problem but hard to scale for large inputs.
</>
Code
from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    n = len(intervals)
    for i in range(n):
        for j in range(i + 1, n):
            # Check if intervals[i] overlaps with intervals[j]
            if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:
                return False
    return True

# Driver code
if __name__ == "__main__":
    print(can_attend_meetings([[0,30],[5,10],[15,20]]))  # False
    print(can_attend_meetings([[7,10],[2,4]]))           # True
Line Notes
for i in range(n):Outer loop picks the first meeting to compare
for j in range(i + 1, n):Inner loop picks the second meeting to compare with the first
if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:Overlap condition: intervals overlap if one's start is before the other's end and vice versa
return FalseReturn immediately if any overlap is found to avoid unnecessary checks
import java.util.*;

public class MeetingRooms {
    public static boolean canAttendMeetings(int[][] intervals) {
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // Check if intervals[i] overlaps with intervals[j]
                if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canAttendMeetings(new int[][]{{0,30},{5,10},{15,20}})); // false
        System.out.println(canAttendMeetings(new int[][]{{7,10},{2,4}}));           // true
    }
}
Line Notes
for (int i = 0; i < n; i++) {Outer loop selects first meeting
for (int j = i + 1; j < n; j++) {Inner loop selects second meeting to compare
if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {Overlap check condition between two intervals
return false;Immediately return false if overlap detected
#include <iostream>
#include <vector>
using namespace std;

bool canAttendMeetings(vector<vector<int>>& intervals) {
    int n = intervals.size();
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            // Check if intervals[i] overlaps with intervals[j]
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                return false;
            }
        }
    }
    return true;
}

int main() {
    vector<vector<int>> intervals1 = {{0,30},{5,10},{15,20}};
    vector<vector<int>> intervals2 = {{7,10},{2,4}};
    cout << boolalpha << canAttendMeetings(intervals1) << endl; // false
    cout << boolalpha << canAttendMeetings(intervals2) << endl; // true
    return 0;
}
Line Notes
for (int i = 0; i < n; i++) {Outer loop picks first interval
for (int j = i + 1; j < n; j++) {Inner loop picks second interval to compare
if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {Overlap condition between two intervals
return false;Return false immediately if overlap found
function canAttendMeetings(intervals) {
    const n = intervals.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            // Check if intervals[i] overlaps with intervals[j]
            if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {
                return false;
            }
        }
    }
    return true;
}

// Test cases
console.log(canAttendMeetings([[0,30],[5,10],[15,20]])); // false
console.log(canAttendMeetings([[7,10],[2,4]]));           // true
Line Notes
for (let i = 0; i < n; i++) {Outer loop selects first meeting
for (let j = i + 1; j < n; j++) {Inner loop selects second meeting to compare
if (intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1]) {Overlap check condition
return false;Return false immediately if overlap detected
⏱
Complexity
TimeO(n^2)
SpaceO(1)

We compare each pair of intervals, leading to n*(n-1)/2 comparisons, which is O(n^2). No extra space besides variables is used.

💡 For n=20 meetings, this means about 190 comparisons, which is manageable, but for n=100000, it becomes 5 billion comparisons, which is too slow.
Interview Verdict: TLE / Use only to introduce

This approach is too slow for large inputs but helps understand the problem and why sorting helps.

🧠
Sorting + Single Pass Overlap Check
💡 Sorting intervals by start time allows us to check overlaps efficiently by only comparing adjacent intervals, reducing complexity drastically.

Intuition

Sort intervals by their start time. Then, check if any interval starts before the previous interval ends. If yes, overlap exists.

Algorithm

  1. Sort the intervals by their start time.
  2. Iterate through the sorted intervals from the second interval onward.
  3. For each interval, check if its start time is less than the end time of the previous interval.
  4. If any overlap is found, return false; otherwise, return true after the loop.
💡 Sorting simplifies the problem so you only need to check consecutive intervals, making the algorithm efficient and easy to implement.
</>
Code
from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i-1][1]:
            return False
    return True

# Driver code
if __name__ == "__main__":
    print(can_attend_meetings([[0,30],[5,10],[15,20]]))  # False
    print(can_attend_meetings([[7,10],[2,4]]))           # True
Line Notes
intervals.sort(key=lambda x: x[0])Sort intervals by start time to bring overlapping intervals next to each other
for i in range(1, len(intervals))Iterate from second interval to compare with previous
if intervals[i][0] < intervals[i-1][1]Check if current interval starts before previous ends, indicating overlap
return FalseReturn false immediately if overlap found
import java.util.*;

public class MeetingRooms {
    public static boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canAttendMeetings(new int[][]{{0,30},{5,10},{15,20}})); // false
        System.out.println(canAttendMeetings(new int[][]{{7,10},{2,4}}));           // true
    }
}
Line Notes
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));Sort intervals by start time using comparator
for (int i = 1; i < intervals.length; i++) {Loop through intervals starting from second
if (intervals[i][0] < intervals[i - 1][1]) {Check if current interval overlaps with previous
return false;Return false immediately if overlap detected
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canAttendMeetings(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    for (int i = 1; i < intervals.size(); i++) {
        if (intervals[i][0] < intervals[i-1][1]) {
            return false;
        }
    }
    return true;
}

int main() {
    vector<vector<int>> intervals1 = {{0,30},{5,10},{15,20}};
    vector<vector<int>> intervals2 = {{7,10},{2,4}};
    cout << boolalpha << canAttendMeetings(intervals1) << endl; // false
    cout << boolalpha << canAttendMeetings(intervals2) << endl; // true
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {Sort intervals by start time using lambda comparator
for (int i = 1; i < intervals.size(); i++) {Iterate from second interval to check overlap
if (intervals[i][0] < intervals[i-1][1]) {Overlap check between current and previous interval
return false;Return false immediately if overlap found
function canAttendMeetings(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    for (let i = 1; i < intervals.length; i++) {
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false;
        }
    }
    return true;
}

// Test cases
console.log(canAttendMeetings([[0,30],[5,10],[15,20]])); // false
console.log(canAttendMeetings([[7,10],[2,4]]));           // true
Line Notes
intervals.sort((a, b) => a[0] - b[0]);Sort intervals by start time to line up meetings chronologically
for (let i = 1; i < intervals.length; i++) {Loop through intervals from second to last
if (intervals[i][0] < intervals[i - 1][1]) {Check if current meeting starts before previous ends
return false;Return false immediately if overlap detected
⏱
Complexity
TimeO(n log n)
SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n). The single pass to check overlaps is O(n). Overall complexity dominated by sorting.

💡 For n=100000, sorting is efficient and checking overlaps is linear, making this approach scalable.
Interview Verdict: Accepted / Optimal for this problem

This approach is efficient and accepted in interviews and coding platforms.

🧠
Sorting + Early Exit with Interval Merging Concept
💡 This approach is similar to the previous but uses the idea of merging intervals to detect overlaps, reinforcing understanding of interval problems.

Intuition

Sort intervals by start time. Iterate and keep track of the end time of the last meeting. If the current meeting starts before the last ends, overlap exists.

Algorithm

  1. Sort intervals by start time.
  2. Initialize a variable to track the end time of the last meeting.
  3. Iterate through intervals, for each check if start time is less than the tracked end time.
  4. If yes, return false; otherwise, update the tracked end time to current interval's end.
  5. Return true if no overlaps found.
💡 This approach uses a single variable to track the last meeting end, making the overlap check intuitive and efficient.
</>
Code
from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    end = float('-inf')
    for interval in intervals:
        if interval[0] < end:
            return False
        end = interval[1]
    return True

# Driver code
if __name__ == "__main__":
    print(can_attend_meetings([[0,30],[5,10],[15,20]]))  # False
    print(can_attend_meetings([[7,10],[2,4]]))           # True
Line Notes
intervals.sort(key=lambda x: x[0])Sort intervals by start time to process in chronological order
end = float('-inf')Initialize end to negative infinity to handle first interval comparison
for interval in intervals:Iterate over each interval in sorted order
if interval[0] < end:Check if current interval starts before last meeting ended, indicating overlap
import java.util.*;

public class MeetingRooms {
    public static boolean canAttendMeetings(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int end = Integer.MIN_VALUE;
        for (int[] interval : intervals) {
            if (interval[0] < end) {
                return false;
            }
            end = interval[1];
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(canAttendMeetings(new int[][]{{0,30},{5,10},{15,20}})); // false
        System.out.println(canAttendMeetings(new int[][]{{7,10},{2,4}}));           // true
    }
}
Line Notes
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));Sort intervals by start time
int end = Integer.MIN_VALUE;Initialize end to smallest integer to compare first interval
for (int[] interval : intervals) {Iterate over each interval
if (interval[0] < end) {Check if current interval starts before last meeting ended
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canAttendMeetings(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    int end = INT_MIN;
    for (auto& interval : intervals) {
        if (interval[0] < end) {
            return false;
        }
        end = interval[1];
    }
    return true;
}

int main() {
    vector<vector<int>> intervals1 = {{0,30},{5,10},{15,20}};
    vector<vector<int>> intervals2 = {{7,10},{2,4}};
    cout << boolalpha << canAttendMeetings(intervals1) << endl; // false
    cout << boolalpha << canAttendMeetings(intervals2) << endl; // true
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {Sort intervals by start time
int end = INT_MIN;Initialize end to minimum int for first comparison
for (auto& interval : intervals) {Iterate over each interval
if (interval[0] < end) {Check if current interval starts before last meeting ended
function canAttendMeetings(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    let end = Number.NEGATIVE_INFINITY;
    for (const interval of intervals) {
        if (interval[0] < end) {
            return false;
        }
        end = interval[1];
    }
    return true;
}

// Test cases
console.log(canAttendMeetings([[0,30],[5,10],[15,20]])); // false
console.log(canAttendMeetings([[7,10],[2,4]]));           // true
Line Notes
intervals.sort((a, b) => a[0] - b[0]);Sort intervals by start time
let end = Number.NEGATIVE_INFINITY;Initialize end to smallest number for first comparison
for (const interval of intervals) {Iterate over each interval
if (interval[0] < end) {Check if current interval starts before last meeting ended
⏱
Complexity
TimeO(n log n)
SpaceO(1) or O(n) depending on sorting implementation

Sorting takes O(n log n), and the single pass to check overlaps is O(n). Overall complexity is dominated by sorting.

💡 This approach is efficient for large inputs and uses minimal extra space.
Interview Verdict: Accepted / Optimal

This approach is optimal and commonly used in interviews for this problem.

📊
All Approaches - One-Glance Tradeoffs
💡 In 95% of interviews, use the sorting + single pass approach because it is efficient, easy to implement, and accepted.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n^2)O(1)NoN/AMention only - never code due to inefficiency
2. Sorting + Single Pass Overlap CheckO(n log n)O(1) or O(n) depending on sortNoN/ACode this approach in interviews
3. Sorting + Early Exit with Interval Merging ConceptO(n log n)O(1) or O(n)NoN/AAlternative coding approach, conceptually useful
💼
Interview Strategy
💡 Use this guide to understand the problem deeply before your interview. Start by clarifying the problem, then explain the brute force approach to show understanding. Next, present the optimized sorting approach and code it carefully. Finally, test your code with edge cases.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Describe the brute force approach and its inefficiency.Step 3: Introduce sorting and explain how it simplifies overlap checks.Step 4: Code the sorting + single pass solution.Step 5: Test with sample and edge cases, explaining your reasoning.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 8min → Test: 2min. Total ~15min

What the Interviewer Tests

The interviewer tests your ability to identify overlaps efficiently, use sorting correctly, and handle edge cases such as touching intervals or zero-length meetings.

Common Follow-ups

  • What if intervals are already sorted? → Skip sorting step.
  • How to handle intervals with same start or end times? → Explain overlap condition carefully.
  • Can you extend this to find minimum number of rooms? → Leads to Meeting Rooms II problem.
  • What if intervals are very large or streaming? → Discuss data structures or online algorithms.
💡 These follow-ups test your understanding of edge cases, input assumptions, and ability to extend the problem.
🔍
Pattern Recognition

When to Use

1) Problem involves intervals with start and end times. 2) Need to detect overlaps or conflicts. 3) Asked if all intervals can be attended or scheduled. 4) Input size requires efficient solution.

Signature Phrases

Can a person attend all meetings?Do any intervals overlap?Check if intervals conflict

NOT This Pattern When

Problems about interval sums or maximum coverage are different patterns.

Similar Problems

Meeting Rooms II - Find minimum number of rooms neededNon-overlapping Intervals - Remove minimum intervals to avoid overlaps

Practice

(1/5)
1. The following code attempts to implement the optimal car pooling solution. Which line contains a subtle bug that can cause incorrect capacity checks?
def carPooling(trips, capacity):
    max_location = 0
    for _, start, end in trips:
        max_location = max(max_location, end)
    diff = [0] * (max_location + 1)
    for num, start, end in trips:
        diff[start] += num
        diff[end] += num  # Bug here
    current_passengers = 0
    for i in range(max_location + 1):
        current_passengers += diff[i]
        if current_passengers > capacity:
            return false
    return true
medium
A. Line that increments diff[end] by num instead of decrementing
B. Line that updates max_location in the first loop
C. Line that increments diff[start] by num
D. Line that checks if current_passengers exceeds capacity

Solution

  1. Step 1: Understand difference array updates

    Passengers boarding at start location increase count; passengers leaving at end location must decrease count.
  2. Step 2: Identify incorrect update

    Line incrementing diff[end] by num adds passengers instead of removing them, causing incorrect capacity calculation.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Increment at end location breaks capacity tracking [OK]
Hint: End location must decrement passengers, not increment [OK]
Common Mistakes:
  • Incrementing instead of decrementing at end
  • Forgetting to update difference array
  • Checking capacity before summing passengers
2. 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
3. What is the time complexity of the binary search + preprocessing approach for the Minimum Interval to Include Each Query problem, given n intervals and m queries?
medium
A. O(n log n + m n log n)
B. O(n log n + m log n * n)
C. O((n + m) log n)
D. O(n * m)

Solution

  1. Step 1: Analyze preprocessing

    Sorting intervals by length takes O(n log n).
  2. Step 2: Analyze per query cost

    For each query, binary search over lengths is O(log n), but coverage check scans up to O(n) intervals, so O(n log n) per query.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Overall complexity is O(n log n + m n log n) due to coverage scanning [OK]
Hint: Coverage check inside binary search causes O(n) scan per query [OK]
Common Mistakes:
  • Assuming coverage check is O(log n) ignoring linear scan
  • Confusing n and m in complexity
  • Forgetting sorting cost
4. What is the time complexity of the sweep line algorithm for finding the minimum number of platforms required given n trains, and why?
medium
A. O(n log n) due to sorting arrivals and departures separately and merging them.
B. O(n^2) because each event is compared with all others to count overlaps.
C. O(n) because we only iterate through arrivals and departures once.
D. O(n log n) because events are sorted and then processed in a single pass.

Solution

  1. Step 1: Identify sorting as the main cost

    We create 2n events and sort them by time, which takes O(n log n).
  2. Step 2: Single pass processing after sorting

    After sorting, we iterate through events once, O(n), updating counts.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates, linear sweep after [OK]
Hint: Sorting events dominates time complexity [OK]
Common Mistakes:
  • Assuming O(n) because of single pass ignoring sorting
  • Confusing nested loops brute force with sweep line
  • Thinking sorting arrivals and departures separately is enough
5. Suppose the problem is modified so that intervals can be reused multiple times for different queries, and queries can be negative integers. Which modification to the binary search + preprocessing approach is necessary to handle this variant correctly and efficiently?
hard
A. Preprocess intervals by length and use a segment tree to query coverage efficiently for negative and repeated queries.
B. No change needed; the original approach works for reuse and negative queries.
C. Sort queries and intervals, use a min-heap to maintain active intervals covering queries in order.
D. Use brute force checking each interval for each query since reuse breaks binary search assumptions.

Solution

  1. Step 1: Identify challenges with reuse and negative queries

    Negative queries require data structures supporting arbitrary ranges; reuse means intervals must be efficiently queried multiple times.
  2. Step 2: Choose appropriate data structure

    Segment tree or interval tree allows efficient coverage queries over any integer range and supports multiple queries efficiently.
  3. Step 3: Why other options fail

    Min-heap approach requires sorting queries and intervals but doesn't handle negative queries well; brute force is inefficient; original approach assumes positive queries and no reuse.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Segment tree supports arbitrary queries and reuse efficiently [OK]
Hint: Segment tree handles arbitrary queries and reuse [OK]
Common Mistakes:
  • Assuming original approach works unchanged
  • Using min-heap without sorting queries
  • Resorting to brute force unnecessarily
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