Meeting Rooms

Problem Description

Given an array of meeting time intervals intervals where intervals[i] = [start, end], determine if a person could attend all meetings.

Examples

Constraints

• 0 ≤ intervals.length ≤ 10⁴
• intervals[i].length == 2
• 0 ≤ start < end ≤ 10⁶

Checking for Schedule Overlaps in Sorted Order

To attend all meetings, there must be no overlapping schedules. A person cannot be in two meetings at the same time.

If we sort the meetings by their start times in ascending order, we can check for overlaps by looking at adjacent meetings. For each meeting starting from index 1, we check if it starts before the previous meeting ends.

• If current_start < previous_end, we have a conflict, and we return false immediately.
• If we scan the entire list without finding any overlaps, we return true.

This reduces the search to a simple O(n log n) sorting step and a linear scan.

Solution 1: Sort and Scan

Sort the intervals array by start time, and then check adjacent elements for overlaps.

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        if (intervals == null || intervals.length <= 1) return true;

        // sort meetings by start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));

        for (int i = 1; i < intervals.length; i++) {
            // check if current meeting starts before the previous one ends
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false; // schedule overlap detected
            }
        }
        return true;
    }
}

class Solution:
    def canAttendMeetings(self, intervals: list[list[int]]) -> bool:
        if len(intervals) <= 1:
            return True

        # sort meetings by start time
        intervals.sort(key=lambda x: x[0])

        for i in range(1, len(intervals)):
            # check if current meeting starts before the previous one ends
            if intervals[i][0] < intervals[i - 1][1]:
                return False  # schedule overlap detected

        return True

#include <vector>
#include <algorithm>

class Solution {
public:
    bool canAttendMeetings(std::vector<std::vector<int>>& intervals) {
        if (intervals.size() <= 1) return true;

        // sort meetings by start time
        std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[0] < b[0];
        });

        for (size_t i = 1; i < intervals.size(); i++) {
            // check if current meeting starts before the previous one ends
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false; // schedule overlap detected
            }
        }
        return true;
    }
};

Complexity Analysis:

• Time Complexity: O(n log n) where n is the number of meetings. Sorting dominates the execution. The scan is a linear O(n) pass.
• Space Complexity: O(1) auxiliary space (excluding memory used by sorting algorithms).

Where it breaks: Nothing breaks for standard ranges. If the start and end coordinates can be equal, the check intervals[i][0] < intervals[i - 1][1] correctly treats adjacent meetings (like [1, 2] and [2, 3]) as non-overlapping.

Common Mistakes

• Not sorting the intervals array first. If the input is unsorted, checking adjacent nodes will miss conflicts between non-adjacent elements.
• Treating back-to-back meetings as overlaps. Back-to-back meetings (e.g. [1, 2] and [2, 3]) do not conflict. The boundary inequality must check strictly less-than < (i.e. start < prev_end), not <=.
• Not handling empty or single-meeting inputs. Verify that the list size is checked at the start to prevent out of bounds errors.

Frequently Asked Questions

What is the difference between Meeting Rooms I and II? Meeting Rooms I (this problem) asks if a single person can attend all meetings (which requires zero overlaps). Meeting Rooms II (LeetCode 253) asks for the minimum number of conference rooms required to hold all meetings simultaneously.

Can we solve this in O(n) time? Only if the coordinate ranges are very small, which would permit bucket sort or counting sort. For general time intervals, sorting is required, setting the lower limit to O(n log n).

What does this problem test in interviews? It tests your capability to sort ranges using custom comparators and detect overlaps in linear lists.

← All Problems