Daily bit(e) of C++ | Merging intervals
Daily bit(e) of C++ #233, Common C++ interview problem: Merging intervals.
Today we will look at a common C++ interview problem: Merging intervals.
Given a list of potentially overlapping intervals (start and end represented by integers), merge all overlapping intervals and return the resulting list of non-overlapping intervals.
Intervals {a,b}, {b,c} are considered overlapping.
For example for the input {{2,3},{0,1},{2,4},{1,2}} the output should be {{0,4}}.
Before you continue reading, I encourage you to try to solve it yourself. Here is a Compiler Explorer link with a couple of test cases: https://compiler-explorer.com/z/3GhjWrG6b.
Solution
When we consider two intervals, they will be in one of the following three configurations:
They do not overlap: one interval is strictly before the other.
They completely overlap: one interval is strictly inside the other.
They partially overlap: only the end of one interval is inside the other.
Considering all these options would be pretty cumbersome. Therefore we want to eliminate some complexity and give some order to the intervals (i.e., sorting them).
If we sort the intervals by their start, we only need to consider the overlaps in one direction. This gives us a more straightforward logic for merging two overlapping intervals: {first.start, std::max(first.end, second.end)}, i.e. if two adjacent intervals overlap, we only have to consider the end times since the start time was already implicitly resolved by the sort.
On top of that, once we merge an interval, it remains in its correct sorted position. Therefore, we can process the entire input in one pass, updating the last interval as long there is an overlap and otherwise inserting the intervals without modification if they do not overlap.
