在C ++中合并范围 [英] Merging Ranges In C++

问题描述

我有一个随机排序的唯一封闭范围R ₀ ... R _n-1 的列表，其中

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 )

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.

推荐答案

您需要做的是:

1. 按字典顺序对范围键为[r_start，r_end]的项目进行排序

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

迭代排序的列表，并检查当前项目是否与下一个项目重叠.如果确实将当前项目扩展为r [i] .start，r [i + 1] .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.

这是示例代码:

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

这篇关于在C ++中合并范围的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！