Meeting Rooms

Problem Statement

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

Examples

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false
Explanation: [0,30] overlaps with both [5,10] and [15,20]

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true
Explanation: No overlaps - person can attend both meetings

Example 3:

Input: intervals = [[0,5],[5,10],[10,15]]
Output: true
Explanation: Meetings are back-to-back with no overlap (touching boundaries are OK)

Constraints

• 0 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= starti < endi <= 10^6

Solution Approach

This is a simpler version of the interval scheduling problem. We need to check if any two meetings overlap.

Key Insight

Sort by start time, then check consecutive meetings for overlap!

If meetings are sorted by start time, overlapping meetings will be adjacent. We only need to check if each meeting starts before the previous one ends.

Algorithm Steps

1. Edge case: If 0 or 1 meetings, return true
2. Sort intervals by start time
3. Iterate through sorted intervals (starting from index 1)
4. Check overlap: If current.start < previous.end, return false
5. Return true if no overlaps found

Why This Works

After sorting by start time:

• If meeting i starts before meeting i-1 ends, they overlap
• We only need to check consecutive pairs (no need to check all pairs)
• Time complexity: O(n log n) for sorting

Example Walkthrough

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

1. Sort by start: [[0,30], [5,10], [15,20]] (already sorted)
2. Check [5,10] vs [0,30]: 5 < 30 → Overlap! Return false

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

1. Sort by start: [[2,4], [7,10]]
2. Check [7,10] vs [2,4]: 7 >= 4 → No overlap
3. Return true

Time & Space Complexity

• Time Complexity: O(n log n)

  • Sorting: O(n log n)
  • Checking overlaps: O(n)
  • Total: O(n log n)

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

  • O(1) if sorting in-place
  • O(log n) for sorting recursion stack

Java Solution

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        // Edge case: empty or single meeting
        if (intervals == null || intervals.length <= 1) {
            return true;
        }

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

        // Check for overlaps
        for (int i = 1; i < intervals.length; i++) {
            // If current meeting starts before previous ends
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false; // Overlap detected
            }
        }

        return true; // No overlaps
    }
}

Python Solution

def canAttendMeetings(intervals: List[List[int]]) -> bool:
    # Edge case
    if not intervals or len(intervals) <= 1:
        return True

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

    # Check for overlaps
    for i in range(1, len(intervals)):
        # If current starts before previous ends
        if intervals[i][0] < intervals[i - 1][1]:
            return False  # Overlap detected

    return True  # No overlaps

Related Problems

• Meeting Rooms II (LeetCode 253): Find minimum meeting rooms needed
• Merge Intervals (LeetCode 56): Merge overlapping intervals
• Non-overlapping Intervals (LeetCode 435): Minimum removals to make non-overlapping
• Insert Interval (LeetCode 57): Insert and merge a new interval

Pattern Recognition

This problem demonstrates:

• Interval Scheduling pattern
• Sort + Scan technique
• Greedy approach (check consecutive pairs only)
• Foundation for more complex interval problems

Common Mistakes

1. ❌ Checking all pairs: O(n²) instead of O(n log n)
2. ❌ Not sorting first
3. ❌ Confusing overlap condition: start < prevEnd (not <=)
4. ❌ Forgetting edge cases (empty, single interval)

Tips for Interviews

• Mention sorting is key to efficiency
• Explain why checking consecutive pairs is sufficient
• Note that [1,5] and [5,10] do NOT overlap (touching is OK)
• Compare with Meeting Rooms II for follow-up
• Time complexity is dominated by sorting