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

Each maintenance entry in windows records the start and end minute of a window, filed in whatever order it was logged, and entries that overlap or touch form one continuous outage. The on-call engineer has to report those outages, earliest first.

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

Example 1

Input:

windows = [{"end":3,"start":1},{"end":6,"start":2},{"end":10,"start":8},{"end":18,"start":15}]

Output:

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

Example 2

Input:

windows = [{"end":4,"start":1},{"end":5,"start":4}]

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 removes that. Once the entries are ordered by start, every range that belongs with the current outage 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 the entries by start

Sorting on the start field guarantees that any entry overlapping the current outage is the very next element, so you never look backward. The entries are records, so the sort needs to be told which field to order by; without it Python has no way to compare two records. Skip the sort entirely and you are stuck comparing all pairs.

Step 2: Seed the first outage

Seed the result with the first sorted entry as a [start, end] pair. Everything after this is a decision: does the next entry join this outage, or start a fresh one.

Step 3: Extend or append

For each remaining entry, if its start is at or before last_end it overlaps or touches, so set the 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 last_end, the gap is genuine, so append a new outage.

The solution

Sort then greedy merge
def merge_windows(windows):
    if not windows:
        return []
    ordered = sorted(windows, key=lambda entry: entry["start"])
    first = ordered[0]
    merged = [[first["start"], first["end"]]]
    for entry in ordered[1:]:
        start, end = entry["start"], entry["end"]
        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