Problem Description

You are given an array of intervals where each interval is represented as a pair [start, end]. Each interval represents a meeting time. Your task is to determine if a person could attend all meetings, i.e., to check if none of the intervals overlap.

Constraints:

• Each interval has a start time and an end time where start < end.
• Return true if a person can attend all meetings (no overlaps), otherwise return false.
• Assume the input is a list of intervals, and intervals may not be sorted.

Thought Process

The core of this problem is to check for overlaps between time intervals. If any two meetings overlap, it is impossible for a single person to attend both.

A brute-force approach would be to compare every pair of intervals to check for overlap. However, this is inefficient as the number of comparisons grows rapidly with the number of meetings.

To optimize, we can first sort the intervals by their start times. Once sorted, we only need to compare each interval with its immediate next neighbor, because if two non-adjacent intervals overlap, then at least one pair of adjacent intervals must also overlap.

This reduces the problem to a simple linear scan after sorting, making the solution much more efficient.

Solution Approach

Here’s a step-by-step guide to solving the problem:

1. Sort the intervals.
   • Sort the list of intervals based on their start time.
   • This ensures that every interval only needs to be checked against the next one for overlap.
2. Check for overlaps.
   • Iterate through the sorted intervals.
   • For each interval, compare its end time with the start time of the next interval.
   • If current.end > next.start, then there is an overlap, and we return false.
   • If no overlaps are found after checking all pairs, return true.

We use sorting because it brings all potentially overlapping intervals next to each other, allowing us to efficiently check for conflicts.

Example Walkthrough

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

1. Sort intervals:
   After sorting by start time: [[0, 30], [5, 10], [15, 20]]
2. Check overlaps:
   • Compare [0, 30] and [5, 10]: 30 > 5 → overlap found!

   Since there is an overlap, the function would return false.

3. Another Example:
   intervals = [[5, 8], [9, 15]]
   • Sort: [[5, 8], [9, 15]]
   • Compare [5, 8] and [9, 15]: 8 <= 9 → no overlap

   No overlaps, so the function returns true.

Code Implementation

class Solution:
    def canAttendMeetings(self, intervals):
        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
      

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

class Solution {
    public 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;
    }
}
      

var canAttendMeetings = function(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;
};
      

Time and Space Complexity

• Brute-force Approach:
  • Compare every interval with every other interval
  • Time Complexity: O(n^2) (where n is the number of intervals)
  • Space Complexity: O(1) (no extra space needed)
• Optimized Approach (Sorting):
  • Sorting the intervals: O(n \log n)
  • Single pass to check overlaps: O(n)
  • Total Time Complexity: O(n \log n)
  • Space Complexity: O(1) if sort is in-place (as in most languages), otherwise O(n) if not

The optimized approach is much more efficient for large input sizes.

Summary

The Meeting Rooms problem is a classic example of interval overlap detection. By sorting the intervals and checking only adjacent pairs, we achieve an efficient solution. The key insight is that sorting brings all potential conflicts next to each other, allowing for a simple linear scan rather than a quadratic number of comparisons. This approach is both elegant and highly performant.