Introduction

Finding overlapping appointments is a classic interval problem. The right complexity depends on exactly what you want and what form the input is already in, because there is an important difference between detecting whether any overlap exists and listing every overlapping pair.

First, Clarify the Complexity Claim

If the appointments are unsorted, an O(n) algorithm is usually not possible in the comparison model. You normally need to sort by start time first, which costs O(n log n).

Linear time becomes realistic in these cases:

• the appointments are already sorted by start time
• the time domain is bounded and you can use a linear-time bucketing strategy

That is the first correction to many online answers. "Find overlaps in O(n)" is only true under extra assumptions.

Detecting Whether Any Overlap Exists

If the appointments are already sorted by start time, detecting whether any overlap exists is easy. Keep track of the latest ending time seen so far. When the next appointment starts before that end time, you found an overlap.

1def has_overlap(appointments):
2    if not appointments:
3        return False
4
5    appointments = sorted(appointments, key=lambda x: x[0])
6    current_end = appointments[0][1]
7
8    for start, end in appointments[1:]:
9        if start < current_end:
10            return True
11        current_end = max(current_end, end)
12
13    return False
14
15
16data = [
17    (9, 10),
18    (10, 11),
19    (10.5, 12),
20]
21
22print(has_overlap(data))

This runs in O(n log n) overall because of sorting, or O(n) after sorting.

The comparison start < current_end assumes an appointment ending at 10:00 does not conflict with one starting exactly at 10:00. If your business rule treats touching endpoints as overlapping, use <= instead.

Finding the Conflicting Windows

Sometimes you do not need every overlapping pair. You just want the merged conflict ranges, which can still be found in a single scan after sorting.

1def conflict_windows(appointments):
2    if not appointments:
3        return []
4
5    appointments = sorted(appointments, key=lambda x: x[0])
6    windows = []
7
8    window_start, window_end = appointments[0]
9    overlap_count = 1
10
11    for start, end in appointments[1:]:
12        if start < window_end:
13            overlap_count += 1
14            window_end = max(window_end, end)
15        else:
16            if overlap_count > 1:
17                windows.append((window_start, window_end))
18            window_start, window_end = start, end
19            overlap_count = 1
20
21    if overlap_count > 1:
22        windows.append((window_start, window_end))
23
24    return windows
25
26
27print(conflict_windows([(9, 11), (10, 12), (13, 14), (13.5, 15)]))

This is still linear after sorting and is often the most useful answer for calendar systems.

Listing Every Overlapping Pair Is Different

If the task is to output every pair of appointments that overlaps, the worst-case output can itself be O(n^2). For example, if every appointment overlaps every other appointment, there are about n^2 / 2 pairs.

That means no algorithm can list all pairs in true O(n) time, because writing the answer already takes quadratic time in the worst case.

This is the second correction many people miss:

• detecting any overlap can be linear after sorting
• listing all overlap pairs cannot beat the size of its own output

So if someone asks for "all overlaps in O(n)," the right response is usually "not in the worst case, unless you change the output format."

Sweep-Line Thinking

The scan above is a simplified sweep-line algorithm. After sorting by time, you move left to right through the day and maintain only the state you still need:

• the farthest end time seen so far
• or a small active set if the reporting requirement is richer

This pattern shows up in:

• meeting schedulers
• room allocation
• booking validation
• CPU interval scheduling

Once the intervals are time-ordered, the problem becomes a one-pass state update rather than repeated pairwise comparison.

Choosing the Right Output

In real systems, the best algorithm is often chosen by output shape:

• boolean answer: "Does any overlap exist?"
• merged ranges: "When is the calendar in conflict?"
• pair list: "Which specific appointments collide?"

Those are not the same computational problem, even though they sound similar in conversation.

If the user interface only needs a warning badge, use the boolean scan. If the UI needs red-highlighted blocks, use merged conflict windows. If the workflow needs explicit conflicting appointment IDs, be prepared for output that can grow quadratically.

Common Pitfalls

• Claiming O(n) without mentioning that unsorted input usually requires sorting first.
• Forgetting to define whether touching endpoints count as overlap.
• Using a quadratic nested loop when a sort-plus-scan approach is enough for detection.
• Asking for every overlapping pair and still expecting linear worst-case time.
• Mixing "find any overlap" with "return all overlaps" as if they were the same problem.

Summary

• For unsorted appointments, the standard solution is sort first, then scan.
• Detecting whether any overlap exists is O(n) after sorting.
• Merged conflict windows can also be found in one pass after sorting.
• Listing every overlapping pair can be O(n^2) in the worst case because the output itself can be that large.
• The right algorithm depends on the exact result you need, not just on the word "overlap."