Where it runs
1. The problem
A meeting room has three bookings for the day: 9:00 to 10:30, 10:00 to 11:00, and 14:00 to 15:00. The first two overlap: the second starts at 10:00, while the first runs until 10:30. So from 9:00 to 11:00 the room is busy as one solid block. The calendar needs exactly such blocks to show the free time between them.
The same task appears in a firewall's routing table (the list of address ranges a network filter checks to decide what to do with a packet). Say it holds the ranges 10 to 25 and 20 to 40. Addresses 20 to 25 are in both. Replace the two with one range, 10 to 40, and the table gets shorter and faster.
In both cases the task is the same. There are many ranges, and some of them overlap or touch. You want the fewest ranges that cover exactly the same points.
This step is part of the paid track
The first 33 steps are open to everyone: lesson, exercise and tests. This one opens with full access. Start with a free account and the free steps.
Create a free accountSee what is includedmergeIntervals([[8, 10], [1, 3], [15, 18], [2, 6], [9, 12], [5, 7]])Merge every pair of intervals that overlap or touch. As given, overlapping intervals can sit far apart.
Recognise it
Say these words and it is this pattern
- merge overlapping intervals
- insert a new interval into a sorted list
- meetings, bookings, or ranges that overlap
- given as [start, end] pairs
- free time / busy time between intervals
Looks similar, isn't
- Sweep line (event counting)
A sweep breaks each interval into two events and counts. Merging keeps the intervals whole.
- Greedy (exchange argument)
Removing the fewest intervals is a greedy choice by end time. Merging only joins what overlaps.
- Sort with a custom comparator
The sort by start is the setup step. This page is about the pass that follows it.
- Difference array
That counts how deep the overlap runs at each index. Merging returns intervals, not counts.
n up to 1e6 costs O(n log n), all of it in the sort. The pass afterwards is O(n).
On LeetCode
Problems with ranges that overlap or touch, where you merge them, insert a new one, or intersect two lists of them. Sort by start, then make one pass that stretches or closes the current range.
This is the lesson task, touching ranges included.
The list is already sorted, so copy what ends before the new range, merge what overlaps it, and copy the rest.
Each number either stretches the current range by one or starts a new range.
Two sorted lists and two pointers, and two current ranges overlap from the larger start to the smaller end.