Meeting Rooms I

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(1)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Single Pass Overlap Check	O(n log n)	O(1) or O(n) depending on sort	No	N/A	Code this approach in interviews
3. Sorting + Early Exit with Interval Merging Concept	O(n log n)	O(1) or O(n)	No	N/A	Alternative 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. You are given a list of intervals and a list of queries. For each query, you need to find the length of the smallest interval that contains that query point. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use a greedy approach by always picking the interval with the earliest start time that covers the query.

B. Use dynamic programming to build a table of minimum intervals covering each possible query point.

C. Sort intervals by their length and use binary search combined with interval coverage checks for each query.

D. For each query, iterate over all intervals and pick the smallest covering interval (brute force).

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the smallest interval covering each query, which suggests sorting intervals by length to efficiently check coverage.

2. Step 2: Identify optimal approach

   Sorting intervals by length and using binary search to limit checks to intervals up to a certain length allows efficient coverage verification for each query.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Binary search on sorted intervals by length is optimal and avoids brute force [OK]

Hint: Sort intervals by length and binary search coverage [OK]

Common Mistakes:

• Assuming greedy earliest start time always works
• Trying DP over all points is inefficient
• Using brute force for large inputs

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 line sweep algorithm for counting intervals containing each point, given n intervals and m points? Assume sorting uses a comparison-based sort.

medium

A. O(n * m)

B. O(n + m)

C. O(n log n + m log m)

D. O((n + m) log (n + m))

Solution

1. Step 1: Identify main operations

   The algorithm creates 2n interval events and m point events, total O(n + m) events.

2. Step 2: Sorting events dominates time

   Sorting O(n + m) events takes O((n + m) log (n + m)) time. The sweep itself is O(n + m).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting all events is the bottleneck, so complexity is O((n+m) log (n+m)) [OK]

Hint: Sorting all events dominates time complexity [OK]

Common Mistakes:

• Assuming O(n*m) from brute force
• Splitting sorting into separate sorts for intervals and points
• Ignoring sorting cost

4. Consider this buggy code snippet for removing covered intervals:

def remove_covered_intervals(intervals):
    intervals.sort(key=lambda x: (x[0], x[1]))  # Bug here
    count = 0
    max_end = 0
    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
    return count

What is the bug in this code?

medium

A. The condition 'if end > max_end' should be 'if end >= max_end' to include equal ends.

B. max_end is not updated correctly inside the loop.

C. Sorting by end ascending instead of descending causes coverage detection failure.

D. The nested loop for coverage check is missing, causing incorrect results.

Solution

1. Step 1: Analyze sorting key

   Sorting by (start ascending, end ascending) orders intervals with same start from shortest to longest, which breaks coverage detection.

2. Step 2: Understand coverage detection logic

   Coverage detection relies on intervals with same start being sorted longest first (end descending) so covered intervals come after.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting end ascending causes missed coverage when starts equal [OK]

Hint: Sort end descending to detect coverage correctly [OK]

Common Mistakes:

• Sorting end ascending instead of descending
• Using strict inequality incorrectly

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