Meeting Rooms

Description

Given an array of meeting time intervals where each interval is represented as [start, end] (with start < end), determine whether a person can attend all the meetings without any scheduling conflicts.

Two meetings conflict if they overlap in time — meaning one meeting begins before another meeting has finished. If no two meetings overlap, the person can attend all of them, and you should return true. Otherwise, return false.

Note that meetings that share an endpoint do not conflict. For example, a meeting ending at time 8 and another starting at time 8 can both be attended — one finishes right as the other begins.

Examples

Example 1

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

Output: false

Explanation: The meeting [0, 30] runs from time 0 to time 30. The meeting [5, 10] starts at time 5, which falls within the first meeting's timespan. Similarly, [15, 20] also starts while [0, 30] is still ongoing. Since meetings overlap, the person cannot attend all of them.

Example 2

Input: intervals = [[5, 8], [9, 15]]

Output: true

Explanation: The first meeting ends at time 8 and the second starts at time 9. There is no overlap — the person finishes the first meeting before the second one begins. All meetings can be attended.

Example 3

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

Output: true

Explanation: Although the input order might suggest they are adjacent, chronologically the meeting [2, 4] occurs first and ends at time 4, well before [7, 10] starts at time 7. No overlap exists.

Constraints

0 ≤ intervals.length ≤ 500
0 ≤ intervals[i].start < intervals[i].end ≤ 1,000,000
Each interval is a pair [start, end] where start is strictly less than end

Editorial

Brute Force

Intuition

The most straightforward approach is to compare every pair of meetings and check if any two of them overlap. If we find even one overlapping pair, we know the person cannot attend all meetings.

Two meetings A and B overlap when they share any common time. Mathematically, two intervals [a_start, a_end] and [b_start, b_end] overlap when the minimum of their end times is greater than the maximum of their start times:

min(a_end, b_end) > max(a_start, b_start)

Think of it like checking your calendar for the entire week: you pick up each appointment and hold it against every other appointment to see if they clash. It's slow, but it's guaranteed to catch every conflict.

Step-by-Step Explanation

Let's trace through with intervals = [[0, 30], [5, 10], [15, 20]]:

Step 1: We have 3 meetings. We need to check all pairs: (0,1), (0,2), (1,2). That's 3 pairs total.

Step 2: Compare meeting 0: [0, 30] with meeting 1: [5, 10].

min(30, 10) = 10
max(0, 5) = 5
Is 10 > 5? YES → these meetings overlap! Meeting [5,10] starts at 5 while [0,30] is still running.

Step 3: Overlap detected — return false immediately. The person cannot attend all meetings.

Let's also trace a non-overlapping case: intervals = [[5, 8], [9, 15]]:

Step 4: Compare meeting 0: [5, 8] with meeting 1: [9, 15].

min(8, 15) = 8
max(5, 9) = 9
Is 8 > 9? NO → no overlap.

Step 5: All pairs checked, no overlap found. Return true.

Brute Force — Checking All Pairs for Overlap — Watch how we compare every pair of meetings to detect overlaps. As soon as one overlap is found, we return false immediately.

Algorithm

Let n be the number of meetings.
For each meeting i from 0 to n-1:
- For each meeting j from i+1 to n-1:
  - Check if meetings i and j overlap using: min(end_i, end_j) > max(start_i, start_j)
  - If they overlap, return false immediately.
If no overlapping pair is found after checking all pairs, return true.

Code

#include <vector>
using namespace std;

class Solution {
public:
    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++) {
                int minEnd = min(intervals[i][1], intervals[j][1]);
                int maxStart = max(intervals[i][0], intervals[j][0]);
                if (minEnd > maxStart) {
                    return false;
                }
            }
        }
        return true;
    }
};

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        n = len(intervals)
        for i in range(n):
            for j in range(i + 1, n):
                a = intervals[i]
                b = intervals[j]
                if min(a[1], b[1]) > max(a[0], b[0]):
                    return False
        return True

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int minEnd = Math.min(intervals[i][1], intervals[j][1]);
                int maxStart = Math.max(intervals[i][0], intervals[j][0]);
                if (minEnd > maxStart) {
                    return false;
                }
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(n²)

We compare every pair of meetings. The total number of pairs is n × (n-1) / 2, which grows quadratically. For each pair, the overlap check is O(1). Total: O(n²).

Space Complexity: O(1)

We only use a few variables for indices and comparisons. No additional data structures are needed.

Why This Approach Is Not Efficient

The brute force approach checks all O(n²) pairs. With n up to 500, that means roughly 125,000 comparisons — manageable for this specific constraint, but the approach doesn't scale well and misses an important structural insight.

The key observation is: if we sort the meetings by start time, any overlap must occur between adjacent meetings in the sorted order. Here's why — if meeting A starts before meeting B (both sorted), and A does not overlap with B, then A definitely cannot overlap with any meeting that starts after B either (since those meetings start even later). This means we only need to check neighboring pairs after sorting.

Sorting costs O(n log n) and then checking adjacent pairs costs O(n), giving us O(n log n) total — a significant improvement over O(n²). The sorting step replaces the need for exhaustive pairwise comparison.

Optimal Approach - Sorting

Intuition

If we arrange all meetings in chronological order (by their start times), detecting conflicts becomes a simple linear scan. After sorting, we just walk through the list and check: does each meeting start after the previous one ends?

Imagine lining up all your appointments on a timeline from left to right. Once they're in order, you only need to check if each appointment starts after the one before it finishes. If any appointment begins while the previous one is still going, there's a conflict.

The overlap condition between two adjacent sorted meetings is simple: if the previous meeting's end time is greater than the next meeting's start time, they overlap. Otherwise, they don't.

Step-by-Step Explanation

Let's trace through with intervals = [[7, 10], [2, 4], [8, 12]]:

Step 1: Sort the intervals by start time.

Before sorting: [[7, 10], [2, 4], [8, 12]]
After sorting: [[2, 4], [7, 10], [8, 12]]

Step 2: Compare adjacent pair 1: [2, 4] and [7, 10].

Does the first meeting end before the second starts?
Check: prev_end = 4, curr_start = 7
Is 4 > 7? NO → no overlap. The first meeting ends 3 time units before the second begins.

Step 3: Compare adjacent pair 2: [7, 10] and [8, 12].

Does the first meeting end before the second starts?
Check: prev_end = 10, curr_start = 8
Is 10 > 8? YES → overlap detected! The meeting [7,10] is still going at time 8 when [8,12] starts.

Step 4: Return false — the person cannot attend all meetings.

Now let's trace a successful case: intervals = [[5, 8], [9, 15]]:

Step 5: Already sorted by start time.

Step 6: Compare [5, 8] and [9, 15]: prev_end = 8, curr_start = 9. Is 8 > 9? NO → no overlap.

Step 7: All adjacent pairs checked, no conflict. Return true.

Sorting-Based Overlap Detection — Adjacent Pair Check — Watch how sorting meetings by start time allows us to detect conflicts by checking only adjacent pairs. This reduces the problem from O(n²) pair comparisons to a single O(n) scan.

Algorithm

If the array has 0 or 1 meetings, return true immediately (no possible conflict).
Sort the intervals array by start time (first element of each interval).
Iterate through the sorted intervals from index 1 to n-1:
- Let prev be the meeting at index i-1 and curr be the meeting at index i.
- If prev.end > curr.start, the two meetings overlap — return false.
If no overlap is found after checking all adjacent pairs, return true.

Code

#include <vector>
#include <algorithm>
using namespace std;

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

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        intervals.sort()
        
        for i in range(1, len(intervals)):
            if intervals[i - 1][1] > intervals[i][0]:
                return False
        
        return True

import java.util.Arrays;

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

Complexity Analysis

Time Complexity: O(n log n)

Sorting the intervals takes O(n log n). The subsequent linear scan to check adjacent pairs takes O(n). The sorting step dominates, giving us O(n log n) overall.

Space Complexity: O(1) or O(log n)

If the sort is done in-place (as is typical for comparison-based sorts in C++ and Java), the only extra space used is O(log n) for the sorting algorithm's recursion stack. No additional data structures proportional to input size are needed. In Python, the built-in Timsort uses O(n) space in the worst case.