The Overlap

A hard Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
hard
Seniority
L5

Problem

Maintenance entries in windows are [start, end] minute ranges filed in whatever order they were logged, and any that overlap or touch describe one continuous outage the on-call engineer has to report. Collapse them into those outages, earliest first.

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

Example 1

Input:

windows = [[1,3],[2,6],[8,10],[15,18]]

Output:

[[1,6],[8,10],[15,18]]

Example 2

Input:

windows = [[1,4],[4,5]]

Output:

[[1,5]]

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.

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
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.

Common follow-up questions