Back to Back

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

Domain
Python
Difficulty
medium
Seniority
L5
Asked in
Uber

Problem

A maintenance-window export hands you a list of [start, end] pairs in intervals, and many of them overlap or sit back to back. Collapse each group of touching ranges into a single span that runs from the earliest start to the latest end of the group, where two ranges count as touching even when one only begins exactly where another finishes. Return the cleaned spans as [start, end] lists ordered by start, and give back an empty list when the input is empty.

Windows stacked on windows. Find the real spans.

Example 1

Input:

intervals = [[1,6],[2,6],[8,10],[15,18]]

Output:

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

Example 2

Input:

intervals = [[1,5],[4,5]]

Output:

[[1,5]]

Worked solution and explanation

What this is really testing

Underneath the scheduling story this is interval coalescing, and the whole problem is rigged by one decision you make before writing any logic: get the intervals into start order. Do that and a single left to right sweep is enough, because every range that could merge with the current one now sits immediately to its right. Skip the ordering and you are chasing overlaps in both directions and the code turns into a mess. The part that actually separates candidates is comparing each new range against the running merged span's end, not the previous input range, so a chain like (1,4),(3,6),(5,9) collapses into (1,9) instead of leaving (5,9) stranded.

Break down the requirements

Step 1: Sort intervals by start time

Sorting by start time brings overlapping intervals next to each other so a single left-to-right pass can merge them.

Step 2: Merge overlapping or adjacent ranges

If the current interval's start is at or before the previous merged interval's end, extend that interval's end to the larger of the two ends. Otherwise, start a new merged interval. Treat adjacency (start == previous end) as overlap.

Step 3: Return sorted non-overlapping intervals

The output should be a list of [start, end] lists in ascending start order. Build each merged interval as a fresh list so you never mutate the caller's input.

The solution

Sort-and-merge with a single scan
def merge_overlapping_time_ranges(intervals):
    if not intervals:
        return []
    sorted_ivs = sorted(intervals, key=lambda x: x[0])
    merged = [[sorted_ivs[0][0], sorted_ivs[0][1]]]
    for i in range(1, len(sorted_ivs)):
        current = sorted_ivs[i]
        last = merged[-1]
        if current[0] <= last[1]:
            if current[1] > last[1]:
                last[1] = current[1]
        else:
            merged.append([current[0], current[1]])
    return merged

Common follow-up questions