The Quiet Hours

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
Tata Consultancy Services

Problem

A monitoring service records maintenance windows as [start, end] minute offsets in windows. The list arrives unsorted, and windows often overlap or fully contain one another. Collapse them into the fewest non-overlapping windows that cover the same time, where two windows that touch at an endpoint count as one continuous window. Return the merged windows sorted from the earliest start.

Overlapping outages hide how much time is really dark. Collapse them into the truth.

Example 1

Input:

windows = [[30,45],[0,20],[10,25]]

Output:

[[0,25],[30,45]]

Example 2

Input:

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

Output:

[[1,8]]

Worked solution and explanation

Why this problem exists in real interviews

This is the merge step of mergesort wearing a maintenance-window costume. The skill being probed: can you take ranges that overlap, touch, or nest, and fold them into one canonical set? Anyone can see that [0,20] and [10,25] should become [0,25]. The trick is doing it without conflating which interval you are extending. The two mistakes that separate candidates are forgetting to order by start first, so out-of-order windows never get a chance to meet, and comparing each window to the next ORIGINAL window instead of the running merged window. Get the second one wrong and [1,5],[2,3],[4,8] never chains into [1,8].

Break down the requirements

Step 1: Order by start so overlaps become neighbors

Once the windows are sorted by start time, two windows can only overlap if they sit next to each other or share an endpoint. That turns a global overlap problem into a local one: you only ever look at the window directly behind you. Input arrives unordered, so this step is not optional. Python compares [start, end] pairs element by element, start first, so a plain sorted(windows) already orders them by start. Windows that share a start get settled by max in the sweep, whatever order they land in.

Step 2: Seed the output with a mutable first window

Copy the earliest window into the result as the first 'current' range. It must be a fresh list, not a reference into the input, because the next step mutates its end in place and you do not want to corrupt the caller's data.

Step 3: Extend the running window, do not assign it

For each following window, if its start is at or before the end of the LAST kept window, they touch or overlap: set that window's end to max(last_end, this_end). The max matters for containment. A nested window like [120,150] inside [100,200] has a smaller end, so a plain assignment would shrink your kept end from 200 to 150. If the start sits past the last end, there is a gap, so append a new range.

The solution

Sort, then sweep folding into the last kept window
def merge_windows(windows):
    if not windows:
        return []
    # Pairs compare by start first, so a plain sort orders the windows by start.
    ordered = sorted(windows)
    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
Naive: compare to the next input window
You check window[i] against window[i+1]. On [1,5],[2,3],[4,8] this links 1-5 with 2-3 but then loses the thread: [4,8] is compared to [2,3], which it does not overlap, so you emit [1,5] and [4,8] separately and never reach [1,8].
Correct: compare to the growing merged window
You always compare the next window against merged[-1], the range you have already extended. After folding [2,3] into [1,5], merged[-1] is still [1,5]; [4,8] overlaps it, so the end stretches to 8 and the three windows correctly collapse into [1,8].

Common follow-up questions