Merging Ranges In C++

Question

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 that perform such a merging operation would be great.

Answer 1

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