When the Hours Touch

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
mid
Asked in
Lyft

Problem

A driver toggles availability throughout a shift, and our status export logs each online stretch as a [start, end] pair of timestamps in seconds (carrying sub-second fractions), unsorted and frequently overlapping because a flaky app reconnects mid-session. Collapse these into the distinct windows the driver was actually online, treating two stretches that overlap or meet exactly end-to-end as one continuous window. Return the windows sorted by start time.

Two sessions that overlap are really one. Find the windows a driver was actually online.

Example 1

Input:

sessions = [[10,30.5],[4.5,12],[40,50.25],[33,42]]

Output:

[[4.5,30.5],[33,50.25]]

Example 2

Input:

sessions = [[0,15],[15,20],[30,35]]

Output:

[[0,20],[30,35]]

Worked solution and explanation

Why this problem exists in real interviews

This is interval coalescing wearing a session-cleanup costume. The skill being probed is whether you know the merge only works AFTER you sort by start time. The data hands you sessions in arrival order, and two overlapping stretches are almost never next to each other, so the candidate who walks the raw list comparing each session to the previous one quietly reports overlapping windows as separate. And because the timestamps are continuous, you cannot dodge the merge by dumping every covered instant into a set and regrouping contiguous points; there is no finite grid to enumerate. Sort by start first and every mergeable pair becomes adjacent; that single invariant is the whole problem.

Break down the requirements

Step 1: Sort by start time to make overlaps adjacent

Sort the sessions on their start value. Once sorted, any session that overlaps an earlier one must overlap the window you are currently building, because nothing with an earlier start is still ahead of you. This is the invariant the whole sweep leans on, and it is exactly what a single pass over the unsorted input fails to establish.

Step 2: Sweep, extending a running window

Seed the result with the first session. For each later session, if its start is less than or equal to the current window's end, it overlaps or touches, so extend the window's end to the max of the two ends. Otherwise it starts a fresh window. The 'less than or equal' is what makes back-to-back sessions like [0.0, 15.0] and [15.0, 20.0] collapse into [0.0, 20.0].

Step 3: Take the max of the ends, not the latest end

When a session is fully contained inside the current window, its end is smaller, so blindly assigning the new end would shrink the window and lose coverage. Always extend with max(current_end, new_end). This is the line that handles [1.0, 100.0] swallowing [20.0, 30.0].

The solution

Sort by start, sweep a running window
def merge_sessions(sessions):
    if not sessions:
        return []
    ordered = sorted(sessions, key=lambda s: s[0])
    merged = [list(ordered[0])]
    for start, end in ordered[1:]:
        last = merged[-1]
        if start <= last[1]:
            last[1] = max(last[1], end)
        else:
            merged.append([start, end])
    return merged
Single pass, no sort
Walk the list in arrival order and compare each session to the previous one. On [[10.0, 30.5], [4.5, 12.0], ...] the [4.5, 12.0] arrives after [10.0, 30.5], so a forward-only scan either emits it as a separate window or extends in the wrong direction and loses the 4.5 start. Wrong answer, and it looks right on already-sorted inputs, which is how it slips through.
Sort then sweep
Sorting guarantees that if a session overlaps anything earlier, it overlaps the window currently being built. One comparison against the last window suffices, and every overlap is caught.

Common follow-up questions