# Merge Intervals

> Overlapping ranges. Merge them.

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

Domain: Python · Difficulty: hard · Seniority: L5

## Problem

Given a list of [start, end] intervals, merge any that overlap or are adjacent. Return the merged list sorted by start ascending. Adjacent means end of one equals start of the next.

## Worked solution and explanation

### Why this problem exists in real interviews

Merging overlapping intervals is a classic **sort-then-scan** algorithm. It tests whether you can identify the sorting invariant and the merge condition in a single clean pass.

> **Trick to Solving**
>
> Sort intervals by start time first. Then scan left to right: if the current interval overlaps the last merged one (its start is within the previous end), extend the previous end. Otherwise, start a new merged interval.

---

### Break down the requirements

#### Step 1: Sort by start time

Sorting ensures that overlapping intervals are adjacent, making a single left-to-right pass sufficient.

#### Step 2: Initialize with the first interval

Add the first sorted interval to the merged result.

#### Step 3: Extend or append

For each subsequent interval, if it overlaps or is adjacent to the last merged interval, extend the end. Otherwise, append it as a new interval.

---

### The solution

**Sort-then-merge with greedy extension**

```python
def merge_intervals(intervals):
    if not intervals:
        return []
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    merged = [sorted_intervals[0]]
    for i in range(1, len(sorted_intervals)):
        current = sorted_intervals[i]
        last = merged[-1]
        if current[0] <= last[1]:
            if current[1] > last[1]:
                merged[-1] = [last[0], current[1]]
        else:
            merged.append(current)
    return merged
```

> **Time and Space Complexity**
>
> **Time:** O(n log n) dominated by sorting. The merge pass is O(n).
> 
> **Space:** O(n) for the sorted copy and the merged result.

> **Interviewers Watch For**
>
> The insight that sorting by start time is the key step. Without sorting, you would need O(n^2) pairwise comparisons.

> **Common Pitfall**
>
> Not handling the case where a later interval is completely contained within an earlier one (e.g., `[1,10]` and `[2,5]`). The `max` on end values handles this.

---

## Common follow-up questions

- How would you insert a new interval into an already-merged list? _(Tests binary search for position and local re-merging.)_
- What if intervals are being added in a stream? _(Tests maintaining a sorted structure (e.g., a balanced BST) for online merging.)_
- How would you count the number of overlapping intervals at any point? _(Tests the sweep line algorithm with start/end events.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/merge_intervals)
- [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.