Problem Description

You are given an array of meeting time intervals, where each interval is represented as intervals[i] = [starti, endi]. Each interval contains a start time and an end time for a meeting. Your task is to determine whether a person can attend all the meetings without any time conflicts.

A person can attend all meetings if no two meetings overlap in time. Two meetings overlap if one meeting starts before the other meeting ends.

For example:

• If you have meetings [0, 30] and [5, 10], these overlap because the second meeting starts at time 5, which is before the first meeting ends at time 30. The person cannot attend both meetings.
• If you have meetings [0, 30] and [35, 50], these don't overlap because the second meeting starts after the first one ends. The person can attend both meetings.

The function should return true if the person can attend all meetings (no overlaps exist), and false if there are any time conflicts between meetings.

Intuition

To check if a person can attend all meetings, we need to ensure no two meetings overlap. The key insight is that if we arrange the meetings in chronological order by their start times, we can simplify the overlap detection process.

Think about how you would manually check your calendar for conflicts. You'd likely look at meetings in the order they occur throughout the day. If any meeting starts before the previous one ends, you know there's a conflict.

By sorting the intervals by start time first, we create a natural timeline of meetings. Once sorted, checking for overlaps becomes straightforward - we only need to compare adjacent meetings. For any two consecutive meetings in the sorted list, if the first meeting ends after the second meeting starts (i.e., end_time_of_first > start_time_of_second), we have an overlap.

The beauty of this approach is that after sorting, we don't need to check every pair of meetings. We only check adjacent pairs because:

• If meeting A comes before meeting B in sorted order (A starts earlier than B)
• And if A doesn't overlap with B
• Then A cannot overlap with any meeting that comes after B either (since those meetings start even later)

This reduces our problem from checking all possible pairs O(n²) to just checking adjacent pairs O(n) after sorting. The condition for no overlap between adjacent meetings is simply: the end time of the earlier meeting must be less than or equal to the start time of the next meeting (a[1] <= b[0]).

Solution Approach

The implementation follows a sorting-based approach to detect meeting conflicts:

1. Sort the intervals: We first sort all meeting intervals based on their start times using intervals.sort(). Since each interval is represented as [start, end], Python's default sorting will compare the first element (start time) of each interval, giving us meetings arranged chronologically.

2. Check adjacent meetings for overlaps: After sorting, we use the pairwise function to iterate through consecutive pairs of meetings. The pairwise(intervals) function creates pairs like (intervals[0], intervals[1]), (intervals[1], intervals[2]), and so on.

3. Overlap detection logic: For each pair of adjacent meetings (a, b) where a comes before b in the sorted order:

   • a[1] represents the end time of the first meeting
   • b[0] represents the start time of the second meeting
   • The condition a[1] <= b[0] checks if the first meeting ends before or exactly when the second meeting starts
   • If this condition is true for all pairs, there are no overlaps

4. Return the result: The all() function returns True if all adjacent pairs satisfy the non-overlapping condition, meaning the person can attend all meetings. If even one pair overlaps (condition returns False), the all() function returns False.

Time Complexity: O(n log n) where n is the number of intervals, dominated by the sorting step.

Space Complexity: O(1) if we don't count the space used by the sorting algorithm (typically O(log n) for the recursion stack in sorting).

The elegance of this solution lies in its use of Python's built-in functions - sort() for ordering, pairwise() for creating adjacent pairs, and all() for checking the condition across all pairs in a single, readable line.

Example Walkthrough

Let's walk through the solution with a concrete example to see how it detects meeting conflicts.

Example Input: intervals = [[7, 10], [2, 4], [8, 12]]

Step 1: Sort the intervals by start time

• Before sorting: [[7, 10], [2, 4], [8, 12]]
• After sorting: [[2, 4], [7, 10], [8, 12]]
• The meetings are now arranged chronologically by when they begin

Step 2: Create pairs of adjacent meetings using pairwise

• The pairwise function generates:
  • Pair 1: ([2, 4], [7, 10])
  • Pair 2: ([7, 10], [8, 12])

Step 3: Check each pair for overlaps

• Pair 1: [2, 4] and [7, 10]

  • Does meeting 1 end before meeting 2 starts?
  • Check: 4 <= 7 → True ✓ (No overlap)

• Pair 2: [7, 10] and [8, 12]

  • Does meeting 1 end before meeting 2 starts?
  • Check: 10 <= 8 → False ✗ (Overlap detected!)
  • Meeting at [7, 10] ends at time 10, but the next meeting [8, 12] starts at time 8
  • These meetings overlap from time 8 to 10

Step 4: Return the result

• Since not all pairs satisfy the non-overlapping condition, all() returns False
• The person cannot attend all meetings due to the conflict between [7, 10] and [8, 12]

Contrasting Example (No conflicts): If we had intervals = [[0, 5], [10, 15], [20, 25]]:

• Already sorted: [[0, 5], [10, 15], [20, 25]]
• Check pairs:
  • 5 <= 10 → True ✓
  • 15 <= 20 → True ✓
• Result: True - person can attend all meetings

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log n)

The time complexity is dominated by the sorting operation intervals.sort(), which takes O(n × log n) time where n is the number of intervals (meetings). After sorting, the code iterates through adjacent pairs using pairwise() and checks if each meeting ends before the next one starts with a[1] <= b[0]. This iteration and comparison takes O(n) time. Therefore, the overall time complexity is O(n × log n) + O(n) = O(n × log n).

Space Complexity: O(log n)

The space complexity comes from the sorting algorithm. Python's built-in sort() uses Timsort, which requires O(log n) space for the recursion stack in the worst case. The pairwise() function creates an iterator that only holds references to consecutive pairs at a time, using O(1) additional space. The all() function also uses O(1) space as it evaluates the generator expression lazily. Therefore, the overall space complexity is O(log n).

Common Pitfalls

1. Confusing Overlap Conditions

One of the most common mistakes is incorrectly defining when two meetings overlap. Students often write:

# INCORRECT - This misses edge cases
if current_meeting[1] >= next_meeting[0]:  # Wrong comparison
    return False

Why it's wrong: Using >= means that meetings like [1, 2] and [2, 3] would be considered overlapping, but they're not! A meeting ending at time 2 and another starting at time 2 means one person can attend both (one ends exactly when the other begins).

Correct approach:

# CORRECT - Meetings overlap only if one ends AFTER the other starts
if current_meeting[1] > next_meeting[0]:
    return False

2. Forgetting to Sort

Another critical mistake is checking for overlaps without sorting first:

# INCORRECT - Checking unsorted intervals
def canAttendMeetings(self, intervals):
    for i in range(len(intervals) - 1):
        if intervals[i][1] > intervals[i + 1][0]:
            return False
    return True

Why it's wrong: Without sorting, you're only checking adjacent meetings in the input order, not chronological order. For example, with input [[7, 10], [2, 4]], this would incorrectly return True because it only checks if [7, 10] overlaps with [2, 4] as given, missing that chronologically [2, 4] comes first.

Solution: Always sort by start time first:

intervals.sort()  # Critical step!

3. Checking All Pairs Instead of Adjacent Pairs

Some implementations unnecessarily check every possible pair of meetings:

# INEFFICIENT - O(n²) time complexity
for i in range(len(intervals)):
    for j in range(i + 1, len(intervals)):
        if intervals[i][1] > intervals[j][0] and intervals[j][1] > intervals[i][0]:
            return False

Why it's inefficient: After sorting, you only need to check consecutive meetings. If meeting A doesn't overlap with meeting B, and B doesn't overlap with C, then A definitely won't overlap with C (since they're sorted by start time).

Optimal approach: Only check adjacent pairs after sorting for O(n log n) complexity instead of O(n²).