Meeting Rooms

easy
IntervalsArrayIntervalSorting

Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i], determine if a person could attend all meetings without any overlap.

Two meetings overlap if one starts before the other ends. Meetings that start exactly when another ends do not overlap (e.g., [0, 5] and [5, 10] are compatible).

Return true if a person can attend all meetings, or false otherwise.

Examples

Example 1

  • Input: intervals = [[0,30],[5,10],[15,20]]
  • Output: false
  • Explanation: The meeting [0,30] overlaps with both [5,10] and [15,20], so it is impossible to attend all three.

Example 2

  • Input: intervals = [[7,10],[2,4]]
  • Output: true
  • Explanation: The meetings [2,4] and [7,10] do not overlap, so both can be attended.

Example 3

  • Input: intervals = [[1,5],[5,10]]
  • Output: true
  • Explanation: The first meeting ends at 5 and the second starts at 5. Since they only touch at a single point, there is no overlap.

Constraints

  • 0 <= intervals.length <= 10^4
  • intervals[i].length == 2
  • 0 <= start_i < end_i <= 10^6

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Sort and Check Adjacent

Intuition

The straightforward approach is to sort the meetings by their start time, then check if any two consecutive meetings overlap. If a meeting starts before the previous one ends, there is a conflict. After sorting, we only need to check adjacent pairs because any non-adjacent overlap would also be caught by an adjacent overlap. This is because if meeting A overlaps with meeting C but not meeting B (where A < B < C by start time), then B must start after A ends but before C starts, which contradicts A overlapping with C.

Algorithm

  1. Sort the intervals by start time.
  2. Iterate from the second interval onward.
  3. For each interval, check if its start time is less than the previous interval's end time.
  4. If any overlap is found, return `false`.
  5. If the loop completes without finding overlaps, return `true`.
TimeO(n log n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());

        for (int i = 1; i < (int)intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }

        return true;
    }
};
Java 21
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][0] < intervals[i - 1][1]) {
                return false;
            }
        }

        return true;
    }
}
Python 3.12
def canAttendMeetings(intervals: List[List[int]]) -> bool:
    intervals.sort()

    for i in range(1, len(intervals)):
        if intervals[i][0] < intervals[i - 1][1]:
            return False

    return True
Go 1.26
import "sort"

func canAttendMeetings(intervals [][]int) bool {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] < intervals[i-1][1] {
            return false
        }
    }

    return true
}
Approach 2

Brute Force (Check All Pairs)

Intuition

The brute force approach compares every pair of meetings to check for overlaps. Two meetings [s1, e1] and [s2, e2] overlap if s1 < e2 and s2 < e1. If any pair overlaps, the person cannot attend all meetings. While simple, this approach has O(n^2) time complexity and is not optimal for large inputs. It is useful as a starting point to understand the problem before optimizing.

Algorithm

  1. For every pair of intervals `(i, j)` where `i < j`:
  2. Check if they overlap: `intervals[i][0] < intervals[j][1]` and `intervals[j][0] < intervals[i][1]`.
  3. If any pair overlaps, return `false`.
  4. If no overlaps found, return `true`.
TimeO(n^2)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
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++) {
                if (intervals[i][0] < intervals[j][1] &&
                    intervals[j][0] < intervals[i][1]) {
                    return false;
                }
            }
        }
        return true;
    }
};
Java 21
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++) {
                if (intervals[i][0] < intervals[j][1] &&
                    intervals[j][0] < intervals[i][1]) {
                    return false;
                }
            }
        }
        return true;
    }
}
Python 3.12
def canAttendMeetings(intervals: List[List[int]]) -> bool:
    n = len(intervals)
    for i in range(n):
        for j in range(i + 1, n):
            if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:
                return False
    return True
Go 1.26
func canAttendMeetings(intervals [][]int) bool {
    n := len(intervals)
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            if intervals[i][0] < intervals[j][1] && intervals[j][0] < intervals[i][1] {
                return false
            }
        }
    }
    return true
}

Frequently asked questions

What is the optimal time complexity of Meeting Rooms?

The most efficient approach in this guide ("Brute Force (Check All Pairs)") runs in O(n^2) time and uses O(1) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Meeting Rooms use?

Meeting Rooms is a easy-level Intervals problem involving Array, Interval, Sorting. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Meeting Rooms be solved without extra space?

The most space-efficient approach in this guide uses O(1) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(1).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Loading editor...
Input
intervals=
[[0,30],[5,10],[15,20]]
Expected Output
false