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:
    def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
        n = len(intervals)
        if n < 2: return True

        intervals.sort(key=lambda x: x[0])
        i, j = 0, 1
        while j < n:
            if intervals[j][0] < intervals[i][1]:
                return False
            i, j = i + 1, j + 1
        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