Why this matters
A calendar app has a list of busy times. Each busy time is a start and an end, such as 09:00 to 10:30. When two busy times overlap or touch, the person is busy for one longer stretch, and the app should show one block instead of two. Merging is the step that combines them. Inserting is the step that adds a new busy time to a list that is already clean.
Both steps are common in real code. They appear in calendar code, in the cleanup of ranges of IP addresses, in the handling of time ranges in logs, and in interview questions. Both are greedy because the walk makes one decision per interval and never goes back. Both need a sort first, or in the insert case a list that is already sorted.
Words you will need
- Interval: a span with a start and an end. This lesson writes an interval as
[start, end]. - Closed interval: an interval that includes both ends.
[1, 3]contains the points 1, 2 and 3, and also every number in between. This is different from the half-open intervals in the activity selection lesson, where the end does not count. - Overlap: two intervals overlap when they share at least one point.
- Touch: two closed intervals touch when one ends at the exact point where the other starts.
[1, 4]and[4, 5]touch at 4. In this lesson, touching counts as overlap, so they merge into[1, 5]. - Block: a merged interval. A block is the result of combining one or more overlapping intervals.
- Sweep: a single walk from left to right through a sorted list. The walk keeps track of the current block and decides, for each interval, whether it extends the block or starts a new one.
- Vector: a C++ container that holds a list of items in one block of memory. It grows as you add items.
The idea: sort, then sweep
Here is a short example. Take four intervals: [1, 3], [2, 6], [8, 10] and [15, 18]. The first two overlap, because they share the points from 2 to 3. The other two stand alone. The merged answer is [1, 6], [8, 10] and [15, 18].
Work it by hand. Start with the first interval, [1, 3], as the current block. Look at [2, 6]. Its start, 2, is at or before the block's end, 3. So they overlap. Extend the block to the larger of the two ends. The block becomes [1, 6]. Look at [8, 10]. Its start, 8, is after the block's end, 6. There is a gap, so this interval starts a new block. Look at [15, 18]. Its start is after 10, so it starts another new block. The answer has three blocks.
The walk only works in this order because the intervals are sorted by start. If the intervals were in a random order, a later interval could overlap an early block from far away, and the one-pass walk would miss it. Sorting by start guarantees that each new interval starts at or after every interval seen before it. So the only block that can overlap a new interval is the current block.
Why sorting by start works
Here is the argument in plain steps. After the sort, the intervals are in order of start. Suppose the walk has built a block that ends at E. Now the walk reaches an interval whose start is after E. Every interval that comes later starts at or after this one, so every later start is also after E. None of the later intervals can reach back to touch the block. The block is finished, and the walk can start a new one.
If instead the new interval starts at or before E, it overlaps the block. The block grows to the larger of its end and the new interval's end. The block still covers only points that some interval covers, because the new interval starts inside the block or at its edge. So the block is never too large.
Together these two facts show that the walk produces the smallest possible list of blocks. Every output block covers exactly the points covered by the intervals that landed in it, and no two output blocks overlap or touch.
The merge rule in one line
For each interval after the first, compare its start with the end of the last block. If the start is after that end, add the interval as a new block. If not, extend the last block's end to the larger of the two ends. The word "larger" matters. An interval can be long enough to end after the last interval seen so far, and the block must keep the farther end.
Program 1: merging intervals in C++
The program reads a list of intervals, sorts them by start, and prints the merged blocks. Type the five-interval input below into the Input box, then press Run. The fifth interval, 3 4, is out of order on purpose, so you can see the sort at work.
5
1 3
2 6
8 10
15 18
3 4The first number is the count. Each following line holds one interval, with its start and then its end.
The output you should see:
[1, 6]
[8, 10]
[15, 18]The code has three parts. The first part reads the intervals into a vector of Interval structs. The second part sorts them by start. The lambda passed to sort is the only ordering rule the program needs. The third part is the sweep. The vector merged holds the blocks found so far. The test it.start > merged.back().end is the decision for each interval. If it is true, the interval starts a new block, and push_back adds it. If it is false, the interval overlaps or touches the last block, and the else branch extends that block.
The max call inside the else branch is the part that beginners most often leave out. It is covered in the third example below.
A second example: touching and unsorted input
The second example has two rules at work. Some intervals touch, and the input is out of order. Take four intervals: [1, 4], [4, 5], [0, 0] and [2, 2]. Before you run it, sort them by start by hand. The sorted order is [0, 0], [1, 4], [2, 2] and [4, 5].
The walk starts with [0, 0]. Next is [1, 4]. Its start, 1, is after 0, so it starts a new block. Next is [2, 2]. Its start, 2, is at or before the block's end, 4, so it sits inside the block and changes nothing. Next is [4, 5]. Its start, 4, equals the block's end, so the two touch. The block grows to end at 5. The answer is [0, 0] and [1, 5].
Here is the run on that input:
4
1 4
4 5
0 0
2 2[0, 0]
[1, 5]The point 4 is in both [1, 4] and [4, 5], so the two merge. If the sign in the test had been >=, the block would have stayed split at 4. The next section shows that mistake.
A third example: a long interval hides short ones
The third example is the one that catches the most mistakes. Take three intervals: [1, 10], [2, 3] and [4, 5]. The first interval is long, and the other two sit inside it.
After sorting by start, the order is the same as the input. The walk starts with [1, 10]. The next interval is [2, 3]. Its start, 2, is at or before 10, so it joins the block. The block should keep the end 10, not change to 3, because the old end is larger. Then [4, 5] starts at 4, which is also inside the block. The block should still end at 10.
The max call makes this work. Each merge keeps the larger of the two ends. Here is the run:
3
1 10
2 3
4 5[1, 10]The output is a single block, because every interval sits inside the long one. If the code copied the new interval's end into the block instead, the block would end at 3 after the second interval, and [4, 5] would start a new block. That is wrong, and the mistakes section below shows what it prints.
Insert one interval into a sorted list
The second problem starts from a list that is already sorted and already merged. Each interval in the list is separate from the others, and the list is in order by start. Now a new interval arrives, and it must be added while keeping the list clean and sorted.
The best approach is one pass with three phases. The list is sorted, so the intervals split into three groups based on where they sit relative to the new interval.
Phase 1 copies every interval that ends before the new interval starts. These intervals sit to the left of the new one and touch nothing, so they are copied as they are.
Phase 2 merges every interval that overlaps the new one. An interval overlaps when it starts at or before the new interval's end. Each one widens the new interval. The new interval's start becomes the smaller of the two starts, and its end becomes the larger of the two ends. After this phase, the new interval has grown to cover everything it touches.
Phase 3 copies every interval that is left. These start after the merged interval ends, so they sit to the right and are copied as they are.
This one pass is enough, because the list is sorted. Phase 1 stops at the first interval that reaches the new one, and Phase 2 stops at the first interval that starts after the new one ends. Nothing needs to be checked twice.
Program 2: inserting an interval in C++
The program reads a sorted list of intervals, then reads one new interval, and prints the list with the new interval inserted. Type the five-interval input below into the Input box, then press Run. The last line holds the new interval, 4 8.
5
1 2
3 5
6 7
8 10
12 16
4 8The output you should see:
[1, 2]
[3, 10]
[12, 16]Look at what happened. The new interval [4, 8] overlaps [3, 5], [6, 7] and [8, 10]. Phase 1 copied [1, 2], because its end 2 is before 4. Phase 2 merged [3, 5], [6, 7] and [8, 10] into the new interval. The start became 3, the smaller start, and the end grew to 10, the largest end in the group. Phase 3 copied [12, 16], because it starts after 10.
The loop conditions are the whole logic. The first loop checks items[i].end < added.start, which is a strict test. An interval that ends exactly where the new one starts touches it, and the second loop must merge it. The second loop checks items[i].start <= added.end, which is the touch rule again. Both tests use the closed-interval convention from the start of this lesson.
The i < items.size() test in each loop is required. Without it the loop would read past the end of the vector.
Two more edge cases
The new interval can land at either end of the list, or the list can be empty. These cases show that the three phases do not need special code.
For the first case, take three intervals [1, 5], [6, 8] and [10, 12], and insert [0, 0]. Phase 1 copies nothing, because no interval ends before 0. Phase 2 merges nothing, because no interval starts at or before 0. Phase 3 copies all three intervals. The new interval [0, 0] is added before them, because the result.push_back(added) line runs before Phase 3. Here is the output:
[0, 0]
[1, 5]
[6, 8]
[10, 12]For the second case, the list is empty. Enter 0 as the count, and then 5 7 as the new interval. Phase 1, Phase 2 and Phase 3 all find nothing to copy, and the new interval is the only item in the output. Insert on an empty list is the same as creating the list with one interval.
Common mistakes
Merging without sorting first. The sweep relies on the order by start. If the input is unsorted, a long block can be closed too early, and a later interval can start a second block where it should join the first. Here is what the sweep prints for three unsorted intervals, [8, 10], [1, 3] and [2, 6], when the sort line is removed:
[8, 10]The output is wrong. The correct answer is [1, 6] and [8, 10], which is what Program 1 prints when the sort line is kept.
Copying the end instead of taking the larger end. A merge that writes merged.back().end = it.end loses the farther end of a long interval. For the three-interval example, [1, 10], [2, 3] and [4, 5], the wrong version prints this output:
[1, 3]
[4, 5]Two separate blocks are printed, and the first one is too short. The correct version prints [1, 10]. Always use max for the end.
Using > where >= is needed, or the other way round. The merge test is it.start > merged.back().end. The strict sign means a start that equals the block's end still merges. Changing it to >= treats touching intervals as separate. For the input [1, 3] and [3, 5], the wrong version prints two blocks:
[1, 3]
[3, 5]The correct version prints [1, 5], because the two intervals share the point 3.
Forgetting that the insert list must already be sorted. The three-phase walk in the insert program depends on the input list being sorted and free of overlaps. If it is not, Phase 1 can stop too early and copy an interval that belongs in the merged block. Sort the list, or merge it first with Program 1, before you insert.
Reading past the end of a vector. A loop such as while (items[i].end < added.start) without the i < items.size() check reads outside the vector when the new interval lies after every existing interval. C++ does not check this for you. The program may print garbage numbers or crash. The check in each loop prevents it.
Leaving the new interval out of the output. Each phase copies items from the list. The new interval is only added when result.push_back(added) runs in between Phase 2 and Phase 3. Forgetting that line drops the new interval from the output, even though the other intervals print correctly.
Practice
Exercise 1. Merge the two intervals [1, 4] and [4, 5]. Do they touch, and what is the result?
Show the answer
They touch at the point 4, so they merge into [1, 5]. In this lesson touching counts as overlap, because the intervals are closed.
Exercise 2. Merge the three intervals [1, 4], [0, 2] and [3, 5]. Sort them by start first, then sweep.
Show the answer
Sorted by start, the order is [0, 2], [1, 4] and [3, 5]. The block starts as [0, 2]. The interval [1, 4] starts at 1, which is at or before 2, so the block grows to end at 4. The interval [3, 5] starts at 3, which is at or before 4, so the block grows to end at 5. The result is [0, 5]. Program 1 prints the same answer on this input.
Exercise 3. Insert the interval [2, 5] into the sorted list [1, 3] and [6, 9]. Which phase copies each interval?
Show the answer
Phase 1 copies nothing, because [1, 3] does not end before 2. Phase 2 merges [1, 3] into the new interval, because [1, 3] starts at or before 5. The merged interval becomes [1, 5]. The interval [6, 9] starts after 5, so Phase 3 copies it as it is. The output is [1, 5] and [6, 9].
Exercise 4. Insert the interval [0, 0] into an empty list. What is printed?
Show the answer
Only [0, 0]. With no existing intervals, every phase finds nothing to copy, except that the new interval is pushed into the result. Program 2 prints this output when the count is 0.
Exercise 5. The block is [1, 5], and the next interval is [4, 6]. Write the test that decides whether [4, 6] joins the block, then give the new block.
Show the answer
The test is 4 > 5. That is false, so [4, 6] overlaps the block and joins it. The block's end becomes the larger of 5 and 6, which is 6. The new block is [1, 6].
Summary
- Sort intervals by start, then one left-to-right sweep merges every overlapping or touching group.
- In the sweep, an interval starts a new block when its start is after the block's end, and otherwise extends the block with
max. - Touching intervals merge, because the lesson uses closed intervals, so the test uses
>rather than>=. - Inserting into a sorted list takes three phases: copy the intervals before, merge the overlapping ones into the new interval, then copy the intervals after.
- Each of the common mistakes shows up as a wrong count of blocks, so check the output on a small case with a touch and a long interval before you trust the code.