The Schedule Cleaner

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
L4
Asked in
Netflix

Problem

You're consolidating playback sessions from a streaming service's event logs, where each session in intervals is a [start, end] timestamp pair that may arrive in any order. Collapse every run of overlapping sessions into one continuous span and return the spans sorted by start time. Sessions that only touch at an endpoint still belong to the same span, so [1, 3] and [3, 5] become [1, 5].

Overlapping sessions. One clean line.

Example

Input:

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

Output:

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

Worked solution and explanation

What this really is

Strip the streaming costume and this is range coalescing: turning a pile of possibly-overlapping sessions into the fewest spans that cover exactly the same time. Anyone can write the comparison between two intervals. What separates candidates is two things. Do they put the sessions in start order before comparing anything? And do they treat a span's end as something that only ever grows? Skip the sort and a later session that arrives first hides a real overlap. Overwrite the end instead of keeping the larger one and a short session nested inside a long one, like [2, 4] inside [1, 10], chops the span down to [1, 4].

Walking the merge

Step 1: Sort by start time

Sorting by start guarantees that any session able to overlap the current span is the very next one you visit. That is what turns an all-pairs comparison into a single forward pass.

Step 2: Keep the last span open

Walk the sorted sessions carrying a list of merged spans. The open span is always the last one you appended, so the only thing you ever compare against is merged[-1].

Step 3: Extend or open

The overlap test is start <= merged[-1][1]. It uses <=, not <, so touching endpoints merge. On overlap, push the end out with max(merged[-1][1], end), so a nested session like [2, 4] inside [1, 10] cannot shrink the span. Otherwise the session opens a new span.

The solution

Sort then linear merge pass
def merge_intervals(intervals):
    merged = []
    for start, end in sorted(intervals):
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

sorted() builds a new list, so the caller's input is never reordered in place.

Common follow-up questions