Problem Statement

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

A person can attend all meetings if and only if no two meetings overlap in time. Note that meetings ending and starting at the exact same time (e.g., [1, 2] and [2, 3]) are not considered overlapping.

Additional information

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

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]. It is impossible to attend all of them.

Example 2:

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

Output: true

Explanation: The meetings [2,4] and [7,10] do not overlap. You can attend both.

Brute Force (Pairwise Comparison)

Intuition

The simplest way to verify if any meetings conflict is to literally check every single meeting against every other meeting.

If we have Meeting A and Meeting B, they overlap if Meeting A starts before Meeting B ends, AND Meeting B starts before Meeting A ends. If we can run a nested loop and check all possible pairs without finding a single overlap, we know the schedule is completely clear!

Algorithm

1. Store the total number of meetings in n.
2. Loop i from 0 to n - 1.
3. For every i, loop j from i + 1 to n - 1. This ensures we check every unique pair exactly once.
4. For each pair intervals[i] and intervals[j], check for an overlap. An overlap exists if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1].
5. If an overlap is found, immediately return False.
6. If both loops finish without finding any overlaps, return True.

def can_attend_meetings(intervals: list[list[int]]) -> bool:
    n = len(intervals)
    
    # Check every unique pair for overlaps
    for i in range(n):
        for j in range(i + 1, n):
            # Two intervals overlap if they both start before the other ends
            if intervals[i][0] < intervals[j][1] and intervals[j][0] < intervals[i][1]:
                return False
                
    return True

Time & Space Complexity

• Time complexity: O(N^2)

• Reason: We use a nested loop to compare every interval with every other interval. For N meetings, this results in roughly (N * (N - 1)) / 2 comparisons, leading to a quadratic runtime. This will be too slow for large inputs.

• Space complexity: O(1)

• Reason: We only use a few integer variables for our loop indices, requiring no extra memory.

Sorting - Optimal

Intuition

We can completely eliminate the need to check every pair by simply organizing our schedule! If we sort the meetings by their start times, they will be lined up in exact chronological order.

Once they are sorted, a meeting can only possibly overlap with the meeting directly next to it. We just iterate through the sorted schedule one time. If the start time of the current meeting is strictly less than the end time of the previous meeting, they overlap, and we can't attend both!

Algorithm

1. Sort the intervals array based on the start time (index 0 of each interval).
2. Iterate i from 1 to the length of the array minus 1.
3. Check if the current meeting starts before the previous meeting ends: intervals[i][0] < intervals[i - 1][1].
4. If it does, we have a scheduling conflict! Return False.
5. If the loop completes successfully, all meetings are clear. Return True.

def can_attend_meetings(intervals: list[list[int]]) -> bool:
    # Sort the meetings chronologically by start time
    intervals.sort(key=lambda x: x[0])
    
    for i in range(1, len(intervals)):
        # If a meeting starts before the previous one finishes, we can't attend
        if intervals[i][0] < intervals[i - 1][1]:
            return False
            
    return True

Time & Space Complexity

• Time complexity: O(N log N)

• Reason: Sorting the array of N intervals takes O(N log N) time. The subsequent linear scan to check adjacent meetings takes O(N) time. The overall runtime is strictly dominated by the sorting step.

• Space complexity: O(N) or O(1)

• Reason: Depending on the language's built-in sorting algorithm (like Python's Timsort), it can take up to O(N) auxiliary space in the worst case.