Given an array of meeting time 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 [5,10] (and with [15,20]), so the person cannot attend all.

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true
Explanation: No overlap; the person can attend all meetings.

Constraints

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

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants

Thinking Process

Sort intervals by start time. After sorting, any overlap must appear between consecutive meetings — if intervals[i].start < intervals[i-1].end, the person is double-booked.

Intervals on timeline sort by start → scan overlaps

Solution — O(n log n) time, O(log n) space

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        for (int i = 1; i < intervals.size(); i++) {
            if (intervals[i][0] < intervals[i - 1][1]) {
                return false;
            }
        }
        return true;
    }
};

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: Sort intervals by start time. After sorting, any overlap must appear between consecutive meetings — if intervals[i].start < intervals[i-1].end, the person is double-booked.

Walkthrough — input intervals = [[0,30],[5,10],[15,20]], expected output false:

[0,30] overlaps with [5,10] (and with [15,20]), so the person cannot attend all.

Time: O(n log n) · Space: O(\log n)

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Sort by start: After sorting, overlaps can only occur between adjacent intervals.
  2. Overlap condition: Current start < previous end ⇒ overlap.
  3. Follow-up: 253. Meeting Rooms II asks for the minimum number of rooms (sweep line or min-heap).

References

Template Reference