# The Quiet Hours > Overlapping outages hide how much time is really dark. Collapse them into the truth. Canonical URL: Domain: Python · Difficulty: medium · Seniority: mid ## Problem A monitoring service records maintenance windows as `[start, end]` minute offsets in `windows`, arriving in no particular order and often overlapping or fully containing 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 windows ordered earliest first. ## 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 Two windows can only overlap if, once sorted by start time, they sit next to each other or share an endpoint. Sorting by the start value turns a global overlap problem into a local one: you only ever have to look at the window directly behind you. Input arrives unordered, so this step is not optional. #### 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** ```python def merge_windows(windows): if not windows: return [] ordered = sorted(windows, key=lambda w: w[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 ``` > **Complexity** > > Time is O(n log n), dominated by the sort; the sweep itself is a single O(n) pass. Space is O(n) for the output list. At the scale a monitoring backend hits, millions of windows per service per day, the sort is the entire cost and the merge is free, so there is no faster shape than 'sort once, walk once'. > **Interviewers Watch For** > > Whether you sort before sweeping (skip it and the algorithm is silently wrong on real input), whether you take max() of the two ends rather than blindly assigning the new end, and whether you state the touching rule out loud: does start == last_end merge or not? A strong candidate names that decision instead of guessing. > **Common Pitfall** > > Writing last[1] = end instead of last[1] = max(last[1], end). It looks right on simple overlaps and passes the easy cases, then quietly truncates the moment a fully nested window shows up, because the inner window's end is smaller. The other classic miss is appending list references from the input and mutating them, which corrupts the caller's windows. **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 - Now return the total number of covered minutes instead of the windows. How does the loop change? _(Tests whether they can accumulate (end - start) over the merged set rather than re-deriving it, and whether they handle touching windows without double counting.)_ - Windows arrive as an unbounded stream sorted by start. Can you emit merged windows without holding them all in memory? _(Tests streaming awareness: you only need to retain the current open window and flush it when a gap appears.)_ - Should [1,3] and [3,5] merge, or are these half-open ranges where 3 is the exclusive end? _(Tests interval-convention awareness: the touching rule flips between <= and < depending on closed vs half-open semantics.)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the-quiet-hours) - [Python Interview Questions](https://datadriven.io/python-interview-questions) - [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep) - [Daily Challenge](https://datadriven.io/daily) --- Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.