Merging Ranges In C++
A simple algorithm would be:
- Sort the ranges by starting values
- Iterate over the ranges from beginning to end, and whenever you find a range that overlaps with the next one, merge them
Boost.Icl might be of use for you.
The library offers a few templates that you may use in your situation:
- interval_set — Implements a set as a set of intervals - merging adjoining intervals.
- separate_interval_set — Implements a set as a set of intervals - leaving adjoining intervals separate
- split_interval_set — implements a set as a set of intervals - on insertion overlapping intervals are split
There is an example for merging intervals with the library :
interval<Time>::type night_and_day(Time(monday, 20,00), Time(tuesday, 20,00));
interval<Time>::type day_and_night(Time(tuesday, 7,00), Time(wednesday, 7,00));
interval<Time>::type next_morning(Time(wednesday, 7,00), Time(wednesday,10,00));
interval<Time>::type next_evening(Time(wednesday,18,00), Time(wednesday,21,00));
// An interval set of type interval_set joins intervals that that overlap or touch each other.
interval_set<Time> joinedTimes;
joinedTimes.insert(night_and_day);
joinedTimes.insert(day_and_night); //overlapping in 'day' [07:00, 20.00)
joinedTimes.insert(next_morning); //touching
joinedTimes.insert(next_evening); //disjoint
cout << "Joined times :" << joinedTimes << endl;
and the output of this algorithm:
Joined times :[mon:20:00,wed:10:00)[wed:18:00,wed:21:00)
And here about complexity of their algorithms:
Time Complexity of Addition
What you need to do is:
Sort items lexicographically where range key is [r_start,r_end]
Iterate the sorted list and check if current item overlaps with next. If it does extend current item to be r[i].start,r[i+1].end, and goto next item. If it doesn't overlap add current to result list and move to next item.
Here is sample code:
vector<pair<int, int> > ranges;
vector<pair<int, int> > result;
sort(ranges.begin(),ranges.end());
vector<pair<int, int> >::iterator it = ranges.begin();
pair<int,int> current = *(it)++;
while (it != ranges.end()){
if (current.second > it->first){ // you might want to change it to >=
current.second = std::max(current.second, it->second);
} else {
result.push_back(current);
current = *(it);
}
it++;
}
result.push_back(current);
O(n*log(n)+2n):
- Make a mapping of
r1_i -> r2_i
, - QuickSort upon the
r1_i
's, - go through the list to select for each
r1_i
-value the largestr2_i
-value, - with that
r2_i
-value you can skip over all subsequentr1_i
's that are smaller thanr2_i