# The Event Overlap Detector

> Overlapping events. The calendar knows.

Canonical URL: <https://datadriven.io/problems/the_event_overlap_detector>

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Given events as a list of [name, start, end], return all pairs [name_a, name_b] where the two events overlap in time (name_a's interval and name_b's interval share at least one instant). Intervals are half-open [start, end): an event ending exactly when another starts does not overlap. Each pair appears exactly once with name_a's interval starting no later than name_b's. Sort output by (start of name_a, start of name_b).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **interval overlap detection**, a critical pattern for scheduling, resource allocation, and conflict resolution. It probes whether a candidate can efficiently determine which pairs of intervals intersect.

> **Trick to Solving**
>
> Two intervals overlap if and only if `start_a < end_b` and `start_b < end_a`. Sorting by start time lets you prune comparisons early.

---

### Break down the requirements

#### Step 1: Sort events by start time

This enables early termination when checking for overlaps.

#### Step 2: Compare each pair of events

For each event, check subsequent events. Stop when a subsequent event starts after the current event ends.

#### Step 3: Collect overlapping pairs

Use strict inequality (boundary touches are not overlaps).

---

### The solution

**Sort-and-scan pairwise overlap detection**

```python
def find_overlaps(events: list) -> list:
    sorted_events = sorted(events, key=lambda e: e['start'])
    overlaps = []
    for i in range(len(sorted_events)):
        for j in range(i + 1, len(sorted_events)):
            if sorted_events[j]['start'] >= sorted_events[i]['end']:
                break
            pair = (sorted_events[i]['name'], sorted_events[j]['name'])
            overlaps.append(pair)
    return overlaps
```

> **Time and Space Complexity**
>
> **Time:** O(n log n + n * k) where k is the average number of overlaps per event. Sorting is O(n log n). The inner loop terminates early for non-overlapping events.
> 
> **Space:** O(n + p) where p is the number of overlapping pairs.

> **Interviewers Watch For**
>
> Whether you sort first. Without sorting, every pair must be checked, giving O(n^2) comparisons with no early termination.

> **Common Pitfall**
>
> Using `<=` instead of `<` for the overlap check. The problem states boundary touches are not overlaps, so `start_a < end_b` (strict) is required.

---

## Common follow-up questions

- How would you find the maximum number of simultaneous overlapping events? _(Tests sweep-line algorithm with event start/end point sorting.)_
- What if events are added in a stream? _(Tests interval tree or segment tree for dynamic overlap queries.)_
- How would you resolve conflicts automatically? _(Tests scheduling algorithms like greedy interval scheduling.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_event_overlap_detector)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.