# Back to Back

> Windows stacked on windows. Find the real spans.

Canonical URL: <https://datadriven.io/problems/back_to_back>

Domain: Python · Difficulty: medium · Seniority: L5

## 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.

## 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**

```python
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
```

> **Time and Space Complexity**
>
> **Time:** O(n log n) for sorting. The merge scan is O(n).
> 
> **Space:** O(n) for the sorted copy and the result list.

> **Interviewers Watch For**
>
> Handling chains and adjacency. Each new interval must be compared against the running merged interval's end, not just the immediately preceding input interval, so chains like (1,4),(3,6),(5,9) collapse into one. Adjacent intervals (start == previous end) must merge too.

> **Common Pitfall**
>
> Forgetting to copy the first interval into a fresh list before mutating its end. Pushing the original sublist and then writing `last[1] = new_end` silently mutates the caller's input. Build each merged interval as a new list.

---

## Common follow-up questions

- What if the input intervals have open and closed boundaries? _(Tests tracking boundary type and adjusting the overlap condition accordingly.)_
- How would you find the gaps between merged intervals? _(Tests computing the complement: the space between consecutive merged intervals.)_
- What if you needed to merge intervals from multiple sources? _(Tests combining all intervals first, then running the merge once on the combined list.)_
- How would you determine the maximum overlap count at any point? _(Tests the sweep line algorithm with event sorting.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/back_to_back)
- [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). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.