## Merging intervals in next-gen C++

Posted: March 8, 2023 in Competitive Programming, Programming Recipes
Tags: , ,

A few weeks ago, I set this problem at Coding Gym: given an array of `intervals` where `intervals[i] = [starti, endi]`, merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Here is an example:

```Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap, merge them into [1,6].
```

In this post I am revisiting this classical problem with next generation C++.

You probably know that a naïve approach is quadratic and consists in checking each interval with the others. When two intervals do overlap, remove the second one from the array and merge both into the first one.

It’s worth reminding how to determine when two intervals overlap. Assuming that `interval1` precedes `interval2`, the magic condition is:

```interval1.end >= interval2.begin
```

For example:

```1 5
3 6
```

`[1 5]` overlaps with `[3 6]`, indeed `5 >= 3`.

To reduce the number of checks, first sort the intervals by the starting point, then check if each interval overlaps only with the next one. Indeed, since the array is sorted, if an interval does not overlap with the next one then it can’t overlap with any. Bingo!

When merging two intervals together, just pay attention to the ending point: it’s the maximum of both. For example:

```2 8
3 5
```

The result is  `[2, max(8, 5)]=[2, 8]`.

The logic applies until we found two disjointed routes. At that point, “commit” the current merged interval and continue. Here is a first C++ solution:

```vector<vector<int>> merge(vector<vector<int>>& intervals)
{
sort(begin(intervals), end(intervals));
vector<int> curr = intervals;
vector<vector<int>> merged;
for (auto i=1u; i<intervals.size(); ++i)
{
if (curr >= intervals[i]) // overlap?
{
curr = max(intervals[i], curr); // update ending point
}
else
{
merged.push_back(curr); // "commit" current merged interval
curr = intervals[i];
}
}
merged.push_back(curr); // last one is not committed yet
return merged;
}
```

The use of `vector<vector<int>>` is because of LeetCode. Here is an in-place variant that uses a `vector<pair<int, int>>`:

```sort(begin(intervals), end(intervals)); // intervals is vector<pair<int, int>>
auto j = 0u;
for (auto i=1u; i<intervals.size(); ++i)
{
if (intervals[j].second >= intervals[i].first) // overlap?
{
intervals[j].second = max(intervals[i].second, intervals[j].second); // keep merging into the current one
}
else
{
++j; // next "assignable" spot
intervals[j] = intervals[i]; // next interval is the new current one
}
}
intervals.resize(j + 1);
```

The two solutions work correctly and might be optimized even further. However, in the rest of the article I will be having some fun with patterns.

Let’s go!

## Playing with patterns

```1 2
4 6
5 8
6 7
9 10
```

I recommend focusing on the first version of the algorithm (not in-place) because I think spotting the pattern is a bit easier.

To spot a pattern, it’s often useful to write down how the algorithm works, maybe some variables evolving or such. Over time, after practicing, you will automatically visualize it in your mind. Sometimes, even when you are not consciously paying attention to the problem itself, an insight might knock at your door. Let me guide you through that I had.

Let’s write down what `curr` looks like while the algorithm runs:

```vector<vector<int>> merge(vector<vector<int>>& intervals)
{
sort(begin(intervals), end(intervals));
vector<int> curr = intervals;
std::cout << curr << " " << curr << "\n"; // <<- PRINT HERE
vector<vector<int>> merged;
for (auto i=1u; i<intervals.size(); ++i)
{
if (curr >= intervals[i])
{
curr = max(intervals[i], curr);
}
else
{
merged.push_back(curr);
curr = intervals[i];
}
std::cout << curr << " " << curr << "\n"; // <<- PRINT HERE
}
merged.push_back(curr); // last one is not committed yet
return merged;
}
```

All eyes on me. Voilà:

```1 2
4 6
4 8
4 8
9 10
```

Do you see the pattern already?

No? Ok, let me take you one step forward.

That “imaginary” array is a trace of both the final and the intermediate values that contribute to assemble `merged`, that is none other than the output of the merging. We distinguish two cases:

• merging is in progress: the overlapping condition is `true` and `curr` is consuming all the next overlapping intervals. It’s an intermediate value;
• otherwise, the overlapping condition is `false` and then `curr` has to be committed to the result. It’s a final value.

Intervals that will be merged together are easy to spot: they share the same starting value.

Suppose you have this array available. How would you find the solution to the problem?

The question might seem silly: we discard intermediate results, don’t we? Let’s jot down a couple of observations:

• we can have an arbitrary number of intermediate values but only one final value;
• for each merging phase, the final value corresponds to the last intermediate value (we just commit it when we found that it does not overlap with the next interval).

At this point, if I may, I would dare to suggest a theory: we go through all the pairs of this imaginary array one by one and we remove all those having the very same first element (interval start) except for the last one. Let me show you an example of this idea:

```1 2  <- keep, since it does not overlap with the next one
4 6  <- remove, since it's being merged and it's not the last
4 8  <- remove, since it's being merged and it's not the last
4 8  <- keep, since it's being merged and it's the last
9 10 <- keep, since it does not overlap with the next one
```

Indeed, we get:

```1 2
4 8
9 10
```

Please take your time to review this process and, if you need, try the logic on other samples.

This leads us to exploring how this imaginary array can be built and pruned.

Let me start from the latter. How would you remove all the intermediate values except for the last one?

Well, two known patterns from the standard library come to the rescue:

```imaginary.erase(begin(imaginary), unique(rbegin(imaginary), rend(imaginary), [](const auto& i1, const auto& i2){
return i1 == i2; // do they share the very same starting point?
}).base());
```

Indeed, `unique` is used to remove equal (defined by us) adjacent pairs of elements but the first. We need to juggle with reverse iterators a bit to remove the last rather than the first.

Now the best part.

How to build `imaginary`?

If you think about it for a moment, `curr` is just an accumulator that is initialized with `intervals` (printed at the beginning).

Then we iterate the other intervals one by one and compare each with the accumulator:

• if they do not overlap, the accumulator is assigned to the ith element (in the algorithm itself, the current accumulator is committed to the result vector);
• if they do overlap, only the ending point of the accumulator is updated (the accumulator is not committed yet).

The imaginary array is a sort of trace of the accumulator. If we had been interested only in the final value, we would have used `accumulate`. However, we want to keep track of intermediate values. It’s a running operation…

That’s a `partial_sum`:

```vector<vector<int>> imaginary;
partial_sum(begin(intervals), end(intervals), back_inserter(imaginary), [](auto curr, auto i){
return curr >= i ? vector{curr, max(curr, i)} : i;
});
```

This works like a charm. However, it costs that extra `imaginary` vector. Can we do better?

Without beating around the bush, we can use ranges (to be honest, range-v3). `views::partial_sum` saves us that intermediate vector. However, at first I struggled with the second part because the combo `unique + reverse + erase` would need the array in any case because of `reverse`.

My result was ugly and useless. It’s not worth sharing it here.

At some point, I noticed one view I was unaware of. Or better, I knew it existed but I was unaware of one subtle detail.

The problem with `views::unique` is that it eliminates all except the first element from every consecutive group of equivalent elements from the range. Just like `std::unique`. It makes sense.

What I didn’t know was that another view does exactly the same thing except for one detail: it keeps the last element only.

That’s an `adjacent_remove_if`:

```sort(intervals);
auto merged = views::partial_sum(intervals, [](auto curr, auto i){
return curr >= i ? std::vector{curr, max(curr, i)} : i;
}) | views::adjacent_remove_if([](auto i1, auto i2){
return i1 == i2;
});
```

Voilà!

Here is the full solution making use of `vector<pair<int, int>>` as input:

```sort(intervals);
auto merged = views::partial_sum(intervals, [](auto curr, auto i){
return curr.second >= i.first ? std::pair{curr.first, max(curr.second, i.second)} : i;
}) | views::adjacent_remove_if([](auto i1, auto i2){
return i1.first == i2.first;
});

for (const auto& [i,j] : merged)
{
std::cout << i << " " << j << "\n";
}
```

Bear in mind that the code above is lazy: when the range-based for loop pulls one interval, `adjacent_remove_if` extracts two from `partial_sum` that makes just two steps forward. And so on.

That was one possible way to merge overlapping intervals in next-gen C++.

## Bonus pattern

When I found this solution, I got the feeling that another one was plain to all.

I was right.

My intuition was: what if I group the intervals that can be merged together?

Consider this example:

```{1, 2}, {4,6}, {5,8}, {6,7}, {9, 10}
```

My idea is to form these three groups:

```{1, 2}
{4,6}, {5,8}, {6,7}
{9, 10}
```

Then, each group can be merged individually and it’s guaranteed that it can’t be merged with any other (because they are sorted, remember?).

Merging each group works this way:

• the starting value corresponds to the starting point of the first pair;
• the ending value corresponds to the maximum of the other ending points.

Grouping things together…mmm…that’s a `chunk_by`! And the predicate is just…the overlapping condition!

We get sorted the second part in multiple ways. For example, `for_each` + `yield` (list comprehension) + `max_element`:

```auto merged = views::chunk_by(intervals, [](const auto& i1, const auto& i2){
return i1.second >= i2.first;
}) | views::for_each([](auto rng){
return yield(std::pair{front(rng).first, *max_element(views::values(rng))});
});
```

The main issue here is that we go through each element…twice! In other words, `chunk_by` makes a group by iterating all the pairs until it finds two that do not satisfy the condition. One iteration. Then, `max_element` does another iteration.

Apart from this, the solution can be useful, for example, to “visualize” which intervals are going to be merged together. Also, the schema prompts another classical pattern: distributing the “merging task” to multiple workers. Clearly, consider just the idea and not the task itself.

## Conclusion

The arrival point is not directly intended for production. However, I am fully convinced that the intellectual journey matters here. This is deliberate practice and we have unlimited possibilities to learn something new.

For example, I learned that `adjacent_remove_if` keeps the last element of multiple adjacent duplicates. My brain played with patterns and this is good. After all, our brain has been made for that.

Anyway, this is not only about learning during the process. Starting from working code, we can achieve even more.

Indeed, I think not only every problem has value, but also every solution.

Do challenge yourself and explore what you are more interested in. What is tickling your curiosity?

For example, do you know if that call to `partial_sum` can be safely parallelized? You know, the update function must be associative. Is this the case or not? Can you prove it?

And what about an in-place version of the algorithm that – somehow – takes advantage of ranges?

Is the range-based solution slower than the others? Can you measure it?

What if we can’t sort the input in advance?

And so on.

There are unlimited possibilities.

I hope you enjoyed the article and I would be glad to hear your thoughts.