What is the brute force approach and complexity for Meeting Rooms?

Check all n(n−1)/2 pairs of meetings for overlap with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Meeting Rooms?

Sort by start; each meeting only needs checking against the previous one with optimal time complexity O(N log N) and space complexity O(1).

How do you identify the pattern for Meeting Rooms?

Look for key signals in the prompt: "list of [start, end] meetings" indicates Interval input → sort first, then walk once.; "attend all" indicates Yes/no question: does ANY overlap exist? We can stop at the first one.; "one person" indicates At most 1 meeting may be active at any time. Meeting Rooms II asks how many are active at once..

Meeting Rooms

Easy·LeetCode #252 PremiumBasic Anchor

LeetCode

Jump:

30-Second Mental ModelIntervals — Scheduling (sort + neighbour check)

Complexity:O(N²)→O(N log N)

Key Insight

Sort the meetings by start time. Then walk through them and check one thing: does this meeting start before the previous meeting ends? If yes, they overlap. If that never happens, there is no clash anywhere.

Core Validity Invariant

Meeting i is fine when it starts at or after the previous meeting ends: intervals[i][0] ≥ intervals[i−1][1]. Equal is fine, because a meeting is over at its end time.

Problem

You get a list of meetings. Meeting i runs from intervals[i][0] to intervals[i][1].

One person wants to go to every meeting. Return true if no two meetings share any time, and false otherwise.

A meeting is over at its end time. So a meeting that ends at 10 and one that starts at 10 do not clash: you walk out of one and into the other.

Input

A list intervals of [start, end] pairs.

Output

true if one person can attend every meeting, false if any two of them overlap.

Example 1

Input: intervals = [[0,30],[5,10],[15,20]]

Output: false

[0,30] is still running when [5,10] starts at 5, so you can't be in both.

Example 2

Input: intervals = [[7,10],[2,4]]

Output: true

[2,4] ends at 4, long before [7,10] starts.

Example 3

Input: intervals = [[5,10],[10,15]]

Output: true

The first meeting is over at 10, exactly when the second one starts. Touching is not overlapping.

Constraints

• 0 ≤ intervals.length ≤ 10^4
• intervals[i].length == 2
• 0 ≤ start < end ≤ 10^6

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
When exactly do two meetings clash? Write the test for two meetings first.
2.
Is a meeting ending at 10 in conflict with one starting at 10?
3.
If I had to check meetings in some order, which order would put clashing meetings next to each other?
4.
After sorting, do I need to compare a meeting with everything before it, or only with one of them?
5.
What should the answer be for zero meetings or one meeting?

Brute force approach

Idea

Two meetings [s1, e1) and [s2, e2) overlap exactly when each one starts before the other one ends: s1 < e2 && s2 < e1. Try every pair. If any pair overlaps, return false.

Thinking process

1
The answer is false as soon as any two meetings share time, so the simplest plan is to look at every pair.
2
For one pair, overlap means neither meeting is fully over before the other starts.
3
Meeting 1 is fully before meeting 2 if e1 ≤ s2. Meeting 2 is fully before meeting 1 if e2 ≤ s1.
4
If neither is true, they overlap: s1 < e2 && s2 < e1. Note the strict <, so touching ends are allowed.

Code & Implementation

brute.cpp

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        int n = intervals.size();
        // Compare every pair of meetings.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int s1 = intervals[i][0], e1 = intervals[i][1];
                int s2 = intervals[j][0], e2 = intervals[j][1];
                // [s1, e1) and [s2, e2) share time only if each one
                // starts before the other one ends.
                if (s1 < e2 && s2 < e1) return false;
            }
        }
        return true;
    }
};

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        int n = intervals.length;
        // Compare every pair of meetings.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int s1 = intervals[i][0], e1 = intervals[i][1];
                int s2 = intervals[j][0], e2 = intervals[j][1];
                // [s1, e1) and [s2, e2) share time only if each one
                // starts before the other one ends.
                if (s1 < e2 && s2 < e1) {
                    return false;
                }
            }
        }
        return true;
    }
}

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        n = len(intervals)
        # Compare every pair of meetings.
        for i in range(n):
            for j in range(i + 1, n):
                s1, e1 = intervals[i][0], intervals[i][1]
                s2, e2 = intervals[j][0], intervals[j][1]
                # [s1, e1) and [s2, e2) share time only if each one
                # starts before the other one ends.
                if s1 < e2 and s2 < e1:
                    return False
        return True

export function canAttendMeetings(intervals: number[][]): boolean {
    const n = intervals.length;
    // Compare every pair of meetings.
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const s1 = intervals[i][0];
            const e1 = intervals[i][1];
            const s2 = intervals[j][0];
            const e2 = intervals[j][1];
            // [s1, e1) and [s2, e2) share time only if each one
            // starts before the other one ends.
            if (s1 < e2 && s2 < e1) {
                return false;
            }
        }
    }
    return true;
}

Complexity

Time O(N²)Space O(1)

With n = 10^4 that is about 5 · 10^7 pair checks. It passes here, but it does not scale, and it ignores the structure that sorting gives us.

Optimized approach

Idea

Start from brute force

Brute force checks every pair of meetings, even pairs that are far apart in time and can't possibly clash.

Find the repeated work

Most of those pair checks are wasted. Once meetings are in start order, a meeting can only clash with the meeting just before it. Checking it against older meetings tells us nothing new.

Define the state — what variables do I need?

intervals (sorted): The meetings in order of start time.
i: The meeting we are checking now. Meetings 0 … i−1 are already known to be clash-free.
intervals[i−1][1]: When the previous meeting ends. This is the latest end time so far, because nothing before it clashed.

Define validity

Meeting i is fine when it starts at or after the previous meeting ends: intervals[i][0] ≥ intervals[i−1][1]. Equal is fine, because a meeting is over at its end time.

Define the transitions — when does each pointer move, and why is it safe?

Before the loop

sort(intervals) by start

After sorting, a meeting can only be blocked by meetings that started earlier, and the one that matters is the last of them.

intervals[i][0] < intervals[i−1][1]

return false

The previous meeting is still running when this one starts. You can't be in both.

intervals[i][0] ≥ intervals[i−1][1]

move on to i + 1

This meeting starts after (or exactly when) the previous one ends. Every earlier meeting ended even sooner, so there is no clash.

What does the current window add to the answer?

Each comparison confirms one more meeting fits into the day. If all n − 1 comparisons pass, the whole list is clash-free.

Code & Implementation

optimal.cpp

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        // Sort by start time, so meetings come in the order they begin.
        sort(intervals.begin(), intervals.end());

        for (int i = 1; i < (int)intervals.size(); i++) {
            // The previous meeting started earlier. If it is still running
            // when this one starts, the two overlap.
            // Equal is fine: a meeting ending at 10 frees you for one at 10.
            if (intervals[i][0] < intervals[i - 1][1]) return false;
        }
        return true;
    }
};

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        // Sort by start time, so meetings come in the order they begin.
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        for (int i = 1; i < intervals.length; i++) {
            // The previous meeting started earlier. If it is still running
            // when this one starts, the two overlap.
            // Equal is fine: a meeting ending at 10 frees you for one at 10.
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
}

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        # Sort by start time, so meetings come in the order they begin.
        intervals.sort(key=lambda x: x[0])

        for i in range(1, len(intervals)):
            # The previous meeting started earlier. If it is still running
            # when this one starts, the two overlap.
            # Equal is fine: a meeting ending at 10 frees you for one at 10.
            if intervals[i][0] < intervals[i - 1][1]:
                return False
        return True

export function canAttendMeetings(intervals: number[][]): boolean {
    // Sort by start time, so meetings come in the order they begin.
    intervals.sort((a, b) => a[0] - b[0]);

    for (let i = 1; i < intervals.length; i++) {
        // The previous meeting started earlier. If it is still running
        // when this one starts, the two overlap.
        // Equal is fine: a meeting ending at 10 frees you for one at 10.
        if (intervals[i][0] < intervals[i - 1][1]) {
            return false;
        }
    }
    return true;
}

Complexity

Time O(N log N)Space O(1)

The sort is the only expensive part. The scan after it is O(N). Only O(1) extra memory; the sort uses O(log N) stack.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Check all n(n−1)/2 pairs of meetings for overlap	O(N²)	O(1)
Optimal	Sort by start; each meeting only needs checking against the previous one	O(N log N)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“list of [start, end] meetings”Interval input → sort first, then walk once.
“attend all”Yes/no question: does ANY overlap exist? We can stop at the first one.
“one person”At most 1 meeting may be active at any time. Meeting Rooms II asks how many are active at once.

Intervals+sort by start+compare with the previous one→Intervals — Scheduling (sort + neighbour check)

This is the anchor of the scheduling sub-pattern. The question is "is the number of meetings running at once ever more than 1?". With one person, sorting and a neighbour check answer it. Meeting Rooms II asks for the maximum number running at once, which needs a sweep or a heap. Merge Intervals uses the same sort but combines overlapping meetings instead of rejecting them.

Don't make this mistake

Treating touching meetings as overlapping

✗ if (intervals[i][0] <= intervals[i - 1][1]) return false;

✓ if (intervals[i][0] < intervals[i - 1][1]) return false;

[5,10] and [10,15] do not overlap: the first meeting is over at 10, and the second starts at 10. With <= you would wrongly return false.

Forgetting to sort

Without sorting, the meeting just before i in the list is not the one just before it in time. [[10,20],[0,5]] has no clash at all, but the unsorted check sees 0 < 20 and wrongly returns false. Always sort first.

Wrong overlap test in the brute force

✗ if (s1 <= s2 && s2 < e1) return false; // only checks one direction

✓ if (s1 < e2 && s2 < e1) return false;

The one-sided test only catches meeting 2 starting inside meeting 1. It misses meeting 1 starting inside meeting 2. The symmetric test catches every case, including one meeting inside the other.

Merging instead of checking (pattern confusion)

This looks like Merge Intervals, so it is tempting to merge everything and compare the counts. That works, but it is extra work and extra space. Here you only need to find one clash: return false at the first one. Also, Merge Intervals treats touching intervals as overlapping ([1,4] and [4,5] merge), while here touching meetings are fine.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Intervals translate into production architectures and low-level memory mechanics.

LLD Architecture