# The Overlap

> Overlapping windows are one outage. Collapse them into the truth.

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

Domain: Python · Difficulty: hard · Seniority: L5

## Problem

Your monitoring system logs server maintenance as `[start, end]` minute ranges, and windows that overlap or sit back-to-back really describe one continuous outage. Collapse the `windows` so any that overlap or touch at an endpoint become a single range, and return them ordered by start time. Two windows touch when one ends exactly where the next begins.

## Worked solution and explanation

### What this really is

Strip the costume and this is a one-dimensional coverage merge: a pile of time ranges that secretly describe fewer, longer ranges. The trap is reaching for O(n^2) pairwise overlap checks, comparing every window against every other. One sort kills that. Once the windows are ordered by start, every range that belongs with the current one sits immediately to its right, so a single greedy pass merges everything. Get the merge condition wrong and you split [1,4] and [4,5] into two outages when they are really one unbroken window.

> **Trick to solving**
>
> Sort by start, then scan once. Keep a running 'last merged' window. If the next window starts on or before the last end, stretch the last end to the larger of the two ends. Otherwise the gap is real, so open a new window.

---

### Walking it

#### Step 1: Sort by start time

Sorting by start time is the whole game: it guarantees that any window overlapping the current one is the very next element, so you never have to look backward. Without it you are stuck comparing all pairs.

#### Step 2: Seed the result

Seed the result with the first sorted window. Everything after this is a decision: does the next window join this one, or start a fresh one.

#### Step 3: Extend or append

For each remaining window, if its start is at or before the last merged end it overlaps or touches, so set the last end to max(last_end, end). The max is critical: a contained window like [2,5] inside [1,10] must not pull the end backward. If it starts after the last end, the gap is genuine, so append it.

---

### The solution

**Sort then greedy merge**

```python
def merge_windows(windows):
    if not windows:
        return []
    ordered = sorted(windows, key=lambda w: w[0])
    merged = [ordered[0]]
    for start, end in ordered[1:]:
        last_start, last_end = merged[-1]
        if start <= last_end:
            merged[-1] = [last_start, max(last_end, end)]
        else:
            merged.append([start, end])
    return merged
```

*One sort, one pass; max(last_end, end) protects contained windows.*

> **Time and space**
>
> **Time:** O(n log n), dominated by the sort. The merge pass is O(n).
> 
> **Space:** O(n) for the sorted copy and the merged output.

> **Interviewers watch for**
>
> The tell is whether you justify the sort before you write it. A senior says out loud 'sorting makes overlaps adjacent, so one pass is enough.' A candidate who jumps straight to nested loops never saw the invariant, and that is what separates the two.

> **Common pitfall**
>
> A later window fully swallowed by an earlier one, like [1,10] then [2,5]. If you blindly assign the new window's end you shrink [1,10] down to [1,5] and erase coverage that was really there. The max(last_end, end) is exactly what stops that.

---

## Common follow-up questions

- How would you insert one new window into an already-merged list cheaply? _(Tests binary search for the insertion point and local re-merging instead of a full re-sort.)_
- What changes if windows arrive in a stream rather than all at once? _(Tests maintaining a sorted structure such as a balanced BST for online merging.)_
- How would you find the moment of maximum concurrent overlap? _(Tests the sweep-line idea with separate start and end events.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_overlap)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.