View on NeetCode
View on LeetCode

Problem

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

Example 1:

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

Example 2:

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

Constraints:

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

Solution

Approach: Sort and Check Overlaps

The key insight is to sort meetings by start time, then check if any consecutive meetings overlap.

Implementation

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        # Sort by start time
        intervals.sort(key=lambda x: x[0])

        # Check if any consecutive meetings overlap
        for i in range(1, len(intervals)):
            if intervals[i][0] < intervals[i-1][1]:
                return False

        return True

Approach 2: One-Liner

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        intervals.sort()
        return all(intervals[i][0] >= intervals[i-1][1] for i in range(1, len(intervals)))

Complexity Analysis

• Time Complexity: O(n log n), where n is the number of intervals. Sorting dominates.
• Space Complexity: O(1), not counting space for sorting.

Key Insights

1. Overlap Definition: Two meetings overlap if one starts before the other ends.

2. Sorted Check: After sorting by start time, we only need to check consecutive pairs.

3. Early Termination: Return false as soon as we find any overlap.

4. Simple Problem: This is the simplest interval problem - just checking for any conflicts.

5. No Overlap: Meetings [a, b] and [c, d] (where a < c) don’t overlap if b <= c.