Merging Ranges In C++

I have a list of randomly ordered unique closed-end ranges R₀...R_n-1 where

R_i = [r1_i, r2_i] (r1_i <= r2_i)

Subsequently some of the ranges overlap (partially or completely) and hence require merging.

My question is, what are the best-of-breed algorithms or techniques used for merging such ranges. Examples of such algorithms or links to libraries t开发者_运维技巧hat perform such a merging operation would be great.

What you need to do is:

1. Sort items lexicographically where range key is [r_start,r_end]

2. 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);

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

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

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 largest r2_i-value,
• with that r2_i-value you can skip over all subsequent r1_i's that are smaller than r2_i

jethro's answer contains an error. It should be

if (current.second > it->first){
    current.second = std::max(current.second, it->second);        
} else { 

My algorithm does not use extra space and is lightweight as well. I have used 2-pointer approach. 'i' keeps increasing while 'j' keeps track of the current element being updated. Here is my code:

bool cmp(Interval a,Interval b)
 {
     return a.start<=b.start;
 }
vector<Interval> Solution::insert(vector<Interval> &intervals, Interval newInterval) {
    int i,j;
    sort(intervals.begin(),intervals.end(),cmp);
    i=1,j=0;
    while(i<intervals.size())
    {
        if(intervals[j].end>=intervals[i].start)  //if overlaps
        {
            intervals[j].end=max(intervals[i].end,intervals[j].end); //change
        }
        else
        {
            j++;
            intervals[j]=intervals[i];  //update it on the same list
        }
        i++;
    }
    intervals.erase(intervals.begin()+j+1,intervals.end());
    return intervals;
}

Interval can be a public class or structure with data members 'start' and 'end'. Happy coding :)

I know that this is a long time after the original accepted answer. But in c++11, we can now construct a priority_queue in the following manner`

priority_queue( const Compare& compare, const Container& cont )

in O(n) comparisons.

Please see https://en.cppreference.com/w/cpp/container/priority_queue/priority_queue for more details.

So we can create a priority_queue(min heap) of pairs in O(n) time. Get the lowest interval in O(1) and pop it in O(log(n)) time. So the overall time complexity is close to O(nlog(n) + 2n) = O(nlogn)