1. Understanding the Problem

You are given an array of meeting time intervals, where each interval is represented as intervals[i] = [start_i, end_i]. Your task is to determine if a person could attend all meetings. If they can attend every meeting without any conflicts, return true. If any meetings overlap, return false.

What is an Overlap?

Two meetings overlap if one starts before the previous one ends. For example, intervals [0, 30] and [5, 10] overlap because the second meeting starts at time 5, well before the first meeting finishes at time 30.

Note: Meetings that touch at boundaries, such as [0, 8] and [8, 10], do not overlap. A person can step directly out of one meeting at time 8 and into the next.

The Core Constraint (The Trap):

The input intervals are usually provided in a completely unsorted order. Comparing random pairs out of order can cause you to miss conflicts or end up writing unnecessarily complex comparison logic.

2. The Naive Approach: Brute-Force Pair Comparison

The most intuitive way to check for conflicts is to pick every interval and compare it against every other interval in the list to see if they overlap.

Trade-off Analysis

While this logic guarantees you will catch any overlap, it is highly inefficient for large calendars:

• Time Complexity: O(N²) — Double nested loops comparing N intervals against each other. If you have thousands of meetings, your program will slow down drastically.
• Space Complexity: O(1) — No extra memory is allocated.

3. The Optimal Approach: Sorting by Start Time (O(N log N) Time)

To pass a senior-level technical interview, we want to achieve an optimal O(N log N) time complexity. We can do this by organizing the timeline first through sorting.

Imagine managing a physical conference room calendar. If all bookings are written on random sticky notes, checking for double-bookings requires holding every note up against every other note. But if you simply order the sticky notes chronologically by their start time, you only ever need to check if a meeting starts before the meeting directly before it finishes!

By sorting all intervals by their start time, we reduce an O(N²) comparison problem into a simple O(N) linear sweep through adjacent pairs.

4. The Logic Step-by-Step

1. Base Case Check: If there are 0 or 1 meetings, return true immediately. There are no other meetings to conflict with.
2. Sort the Intervals: Sort the array of intervals in ascending order based on their starting times (start_i).
3. Check Adjacent Meetings: Iterate through the sorted list starting from the second meeting (index 1) up to the end:
   • Compare the current meeting's start time with the previous meeting's end time.
   • The Conflict Check: If current_meeting.start < previous_meeting.end, there is an overlap! Return false immediately.
4. If you check every adjacent pair without finding any conflicts, it means all meetings are cleanly scheduled. Return true.

5. Complexity Analysis

• Time Complexity: O(N log N) — Sorting the intervals array of length N takes O(N log N) time. The subsequent linear check takes O(N) time. The overall time complexity is dominated by the sort, giving us O(N log N).
• Space Complexity: O(1) or O(N) — Depending on the programming language and implementation. In-place sorting algorithms use O(1) extra space, while others may take O(N) auxiliary memory for sorting.

6. Code Implementations

Expand the sections below to see the optimal O(N log N) "Sorting" implementations across different languages.

class Solution:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        # Sort intervals by their start times
        intervals.sort(key=lambda x: x[0])
        
        # Check adjacent meetings for overlap
        for i in range(1, len(intervals)):
            prev_end = intervals[i - 1][1]
            curr_start = intervals[i][0]
            
            # If the current meeting starts before the previous one ends, conflict!
            if curr_start < prev_end:
                return False
                
        return True

import java.util.Arrays;

class Solution {
    public boolean canAttendMeetings(int[][] intervals) {
        // Sort intervals based on start time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        // Compare adjacent intervals
        for (int i = 1; i < intervals.length; i++) {
            int prevEnd = intervals[i - 1][1];
            int currStart = intervals[i][0];
            
            // Overlap detected
            if (currStart < prevEnd) {
                return false;
            }
        }
        
        return true;
    }
}

#include <vector>
#include <algorithm>

class Solution {
public:
    bool canAttendMeetings(std::vector<std::vector<int>>& intervals) {
        if (intervals.empty()) return true;
        
        // Sort intervals based on start time
        std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
            return a[0] < b[0];
        });
        
        // Check adjacent pairs for overlap
        for (size_t i = 1; i < intervals.size(); ++i) {
            int prevEnd = intervals[i - 1][1];
            int currStart = intervals[i][0];
            
            if (currStart < prevEnd) {
                return false;
            }
        }
        
        return true;
    }
};

7. Conclusion: You Are Ready

Congratulations, you have just mastered the foundational problem in Interval scheduling! Sorting intervals by start time is the universal first step for almost every interval problem you will encounter in interviews. By organizing the inputs chronologically, you eliminated redundant pair comparisons and reduced a complex O(N²) problem to a sleek O(N log N) solution. Keep this sorting technique ready, as it is the exact foundation used to solve more advanced questions like Meeting Rooms II, Merge Intervals, and Non-overlapping Intervals!