cf.completefrontend
GREEDY & INTERVALS · CORE

Merging overlapping intervals

Sort ranges by their start, then join each one into the previous range when they overlap, giving a short list of ranges that don't overlap.

Time O(n log n)Space O(n)6 practice problemsStep-through picture

The idea

Many inputs are ranges written as [start, end]: highlighted text from character 4 to 9, a video selection from second 12 to 30, a booked slot from 10:00 to 11:00. When ranges overlap, you often want to join them, so [1, 4] and [3, 7] become [1, 7].

The trick is to sort the ranges by their start. After sorting, a range can only overlap the range just before it (or the merged range built so far), never one further back. So you walk the sorted list once, keeping a list merged. If the next range starts before the last merged range ends, stretch the last range's end. Otherwise, start a new merged range.

The result is the smallest list of ranges that covers exactly the same points, sorted, with gaps between them. Many range questions become easy after this step: total covered length, free time between bookings, or whether two ranges collide at all.

An everyday example

Laying strips of tape on a ruler

You have strips of tape to stick along a ruler, each from one mark to another. You lay them in order of where they start. If the next strip starts before the tape you've already laid ends, it just extends the taped stretch (or hides under it). If it starts after a gap, it begins a new taped stretch. At the end, the ruler shows a few solid taped stretches with gaps between them.

How the example maps to the code
In the exampleIn the code
Laying strips by where they startsorted by a[0] - b[0]
The stretch of tape you're buildinglast = merged[merged.length - 1]
The next strip starts before the tape endsstart <= last[1]
Extending the taped stretchlast[1] = Math.max(last[1], end)
Starting a new stretch after a gapmerged.push([start, end])

From the slow way to merging overlapping intervals

  1. The slow way compares every pair of ranges. Whenever two overlap, join them and start over, because the joined range may now overlap others. One round of pair checks costs O(n^2), and you may need up to n rounds, so the work can reach O(n^3).
  2. The waste comes from checking pairs that can't overlap. In random order, any two ranges might touch, so you have to check them all. But after sorting by start, the ranges that can touch a given range sit right next to it in the list.
  3. So sort by start and walk the list, keeping the ranges built so far in merged. The next range starts at or after every range already seen. It can only reach back into the most recent merged range, last, because all the earlier merged ranges end before last begins.
  4. That leaves two cases at each step. If start <= last[1], the new range overlaps or touches last, so stretch last[1] to whichever end is further. If not, there is a gap, and the new range starts a new merged range. That loop is merging overlapping intervals.

How it works

  1. If there are no intervals, return an empty list.
  2. Sort a copy of the intervals by start.
  3. Put a copy of the first interval in merged.
  4. For each next interval [start, end], look at last, the last range in merged.
  5. If start <= last[1], the two overlap (or touch): stretch last[1] to Math.max(last[1], end).
  6. Otherwise there's a gap: push [start, end] as a new range.
  7. Return merged.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function mergeRanges(intervals) {
  2. if (intervals.length === 0) return [];
  3. const sorted = [...intervals].sort((a, b) => a[0] - b[0]);
  4. const merged = [[...sorted[0]]];
  5. for (let i = 1; i < sorted.length; i++) {
  6. const [start, end] = sorted[i];
  7. const last = merged[merged.length - 1];
  8. if (start <= last[1]) {
  9. last[1] = Math.max(last[1], end);
  10. } else {
  11. merged.push([start, end]);
  12. }
  13. }
  14. return merged;
  15. }

How fast it is

TimeO(n log n)
Extra memoryO(n)

Sorting costs O(n log n). The merge pass looks at each range once. The sorted copy and the result each hold up to n ranges.

  • Best caseO(n)

    The ranges are already sorted by start. V8's TimSort finishes in one pass, and the merge is another pass.

  • Average caseO(n log n)

    Ranges in random order: sorting costs O(n log n) and the merge pass O(n).

  • Worst caseO(n log n)

    Any unsorted input. How many ranges merge doesn't matter, since each range is compared with last once.

Common mistakes

  • Forgetting to sort first. Without sorting, [1, 2], [5, 6], [2, 5] would never be joined into one range.
  • Setting last[1] = end instead of Math.max(last[1], end), which shrinks a range when a smaller range sits inside it.
  • Pushing the caller's own interval arrays into merged and then changing them, which silently edits the input.
  • Using < when touching ranges should merge, or <= when they shouldn't. Check whether the end is included.

When to use it

Look for these clues in a problem:

  • The input is a list of ranges, and the question mentions overlap, union, or covered length.
  • You need to join, combine, or simplify ranges, such as selections, highlights, or bookings.
  • You need the gaps between ranges: free time, unselected parts, empty space.
  • The ranges come in any order, and the answer should be sorted ranges that don't overlap.

Check yourself

Answer each one in your head first, then open it.

Why is comparing the new range with last enough?

After sorting by start, every merged range before last ends before last starts, so it also ends before the new range starts. Only last can overlap the new range.

What goes wrong with last[1] = end instead of Math.max(last[1], end)?

A range inside last shrinks it. For [1, 10] then [3, 4], the result becomes [1, 4], and the points from 4 to 10 are lost.

Why copy the first range with [...sorted[0]] instead of pushing it directly?

The loop changes last[1]. Without the copy, that would change the caller's own range array.

If none of the n ranges overlap or touch, how long is merged?

n: every step finds a gap and pushes a new range.

Could this loop work with the ranges sorted by end instead of start?

No. A range that starts very early could come late and overlap several merged ranges, not just last. For [[2, 3], [4, 5], [1, 6]] sorted by end, it returns [[2, 3], [4, 6]] instead of [[1, 6]].

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 6 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The rule the loop keeps: after handling sorted[0] to sorted[i], the ranges in merged are in order, no two of them overlap or touch, and together they cover exactly the same points as sorted[0] to sorted[i]. At the start, merged holds a copy of the first range, so the rule is true.

Each step keeps the rule. Every merged range before last ends before last starts, and last starts at or before the new start because of the sort, so the new range can only overlap last. If it does, setting last[1] to Math.max(last[1], end) adds exactly the new points. If it doesn't, the new range lies wholly after last, and pushing it keeps merged in order with a gap between.

The loop ends after n - 1 steps, and then the rule covers the whole input. merged covers the same points as all the ranges, and no two of its ranges overlap or touch, so none of them could be joined further. That makes it the smallest list of ranges with that coverage.

Going deeper

3 more ideas

Why only the last merged range matters

After sorting by start, every later interval starts at or after the current one. The merged ranges before last all end before last starts (that's why they're separate), so they end before the current interval starts too. The current interval can only overlap last. That's why one pass with a look at last is enough.

Why Math.max when stretching

An interval can sit completely inside the last range, like [2, 3] inside [1, 6]. Setting last[1] = end would shrink the range to [1, 3] and lose 3 to 6. Math.max(last[1], end) only ever makes the range longer.

Touching ranges and the cost

With start <= last[1], [1, 3] and [3, 5] merge into [1, 5], which suits closed ranges where 3 belongs to both. If ranges are half-open (the end isn't included) and touching ranges should stay apart, use start < last[1]. Sorting costs O(n log n) and the pass is O(n).

Work it by hand

Every step in a table, with why

Merge 6 ranges given in mixed order. One range sits inside another, and two only touch at an end.

intervals = [[6, 8], [1, 4], [11, 13], [3, 5], [2, 3], [8, 9]]

Stepi[start, end]laststart <= last[1]mergedWhat happensWhy
1----[[1, 4]]sort, copy the firstSorted by start: [1, 4], [2, 3], [3, 5], [6, 8], [8, 9], [11, 13]. A copy of the first range starts merged.
21[2, 3][1, 4]2 <= 4[[1, 4]]Math.max(4, 3) keeps 4[2, 3] sits inside [1, 4]. Math.max keeps the end at 4; writing last[1] = end would shrink it to 3.
32[3, 5][1, 4]3 <= 4[[1, 5]]stretch the end to 5It overlaps from 3 to 4 and reaches further, so last grows to [1, 5].
43[6, 8][1, 5]6 <= 5 is false[[1, 5], [6, 8]]gap: pushNothing covers the gap from 5 to 6, so a new merged range starts.
54[8, 9][6, 8]8 <= 8[[1, 5], [6, 9]]touching: stretch to 9The two ranges share only the point 8. With <=, touching ranges merge.
65[11, 13][6, 9]11 <= 9 is false[[1, 5], [6, 9], [11, 13]]gap: pushAnother gap, so another new range. This was the last range, so the loop ends.

It returns [[1, 5], [6, 9], [11, 13]]: 6 ranges became 3. After the sort, each range was compared with last exactly once.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Merging overlapping intervalsO(n log n)O(n)Ranges come in any order and you want the fewest ranges that cover the same points.
Insert into an already merged listO(n)O(n)The list is already merged and ranges arrive one at a time, like a user adding text highlights.
Difference array over time unitsO(n + T)O(T)Times are small whole numbers, like minutes in a day, so T is small, and you also want to know which units are covered.
Join pairs until nothing changesO(n^3)O(n)Never in practice. It's only the slow starting point that shows why sorting helps.

Extra memory: O(n): the sorted copy holds n ranges, and merged holds up to n ranges when nothing overlaps.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Merging overlapping intervals and the other approaches, on a scale where each line up is 10 times more steps.
  • Merging overlapping intervals O(n log n)
  • Insert into an already merged list O(n)
  • Difference array over time units O(n + T)
  • Join pairs until nothing changes O(n^3)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Merging overlapping intervals339,96620 million
Insert into an already merged list101,0001 million
Difference array over time units202,0002 million
Join pairs until nothing changes1,0001 billionmore than a quadrillion

Inputs that need care

6 tricky inputs
No ranges: []
The first line returns []. Without it, sorted[0] would be undefined and [...sorted[0]] would throw.
One range: [[4, 9]]
merged starts as [[4, 9]] and the loop never runs. It returns a copy, not the caller's array.
A range inside another: [[1, 10], [3, 4]]
Math.max(10, 4) keeps the end at 10, so the result is [[1, 10]].
Touching ranges: [[1, 3], [3, 5]]
3 <= 3 is true, so they merge to [[1, 5]]. For half-open ranges, where the end isn't included, use start < last[1] to keep them apart.
Many ranges with the same start: [[2, 3], [2, 8], [2, 5]]
They overlap last one after another, and Math.max keeps the biggest end, so the result is [[2, 8]].
A range written backwards: [[7, 2], [3, 4]]
The code assumes start <= end. Here it returns [[3, 4], [7, 2]], though [2, 7] covers [3, 4]. Fix each range with Math.min and Math.max before merging.

Variations and follow-ups

Twists interviewers add

Insert one range into a merged list

If the list is already merged and sorted, don't sort again. Copy every range that ends before the new one starts, join every range that overlaps it into one, then copy the rest. That is one pass, O(n).

Free time between bookings

Merge everyone's busy ranges. The gaps between neighbors in merged, from merged[i][1] to merged[i + 1][0], are the free slots.

Overlap of two merged lists

Given two lists that are each merged and sorted, walk both with two pointers. The overlap of the current pair runs from the larger start to the smaller end, if that isn't empty. Then move past whichever range ends first.

Total covered length

Merge first, then add up end - start for each merged range. Without merging, the overlapping parts would be counted twice.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "merge overlapping", "total time covered", "free slots", or "can one person attend every meeting". The last one is a merge where any overlap means the answer is no.
  • Explain why sorting by start makes one pass enough: after sorting, a new range can only overlap the last merged range. Say this before coding, because it's the whole idea.
  • Ask whether touching ranges like [1, 3] and [3, 5] should merge. The answer decides <= versus <.
  • Test by hand: an empty list, a range inside another, and touching ranges. A common follow-up is "insert one new range into a sorted, merged list": do it in one O(n) pass without sorting.

Where frontend code uses it

The same idea in real UI code
  • A rich-text editor stores bold or highlighted ranges as [start, end] offsets and merges them when a user highlights text that touches an existing highlight.
  • A video editor or player merges selected time ranges, and the browser's HTMLMediaElement.buffered property reports buffered media as a list of ranges that don't overlap.
  • A booking calendar merges busy slots from several calendars before showing free time.

Related algorithms