Merging Ranges In C++(在 C++ 中合并范围)
问题描述
我有一个随机排序的唯一封闭范围列表 R0...Rn-1 其中
I have a list of randomly ordered unique closed-end ranges R0...Rn-1 where
Ri = [r1i, r2i] (r1i <= r2i)
Ri = [r1i, r2i] (r1i <= r2i)
随后一些范围重叠(部分或完全),因此需要合并.
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.
推荐答案
你需要做的是:
按字典顺序对范围键为 [r_start,r_end] 的项目进行排序
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++ 中合并范围的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持编程学习网!
本文标题为:在 C++ 中合并范围
基础教程推荐
- C++ 程序在执行 std::string 分配时总是崩溃 2022-01-01
- 运算符重载的基本规则和习语是什么? 2022-10-31
- 您如何将 CreateThread 用于属于类成员的函数? 2021-01-01
- 调用std::Package_TASK::Get_Future()时可能出现争用情况 2022-12-17
- 如何定义双括号/双迭代器运算符,类似于向量的向量? 2022-01-01
- C++,'if' 表达式中的变量声明 2021-01-01
- 什么是T&&(双与号)在 C++11 中是什么意思? 2022-11-04
- 如何在 C++ 中处理或避免堆栈溢出 2022-01-01
- C++ 标准:取消引用 NULL 指针以获取引用? 2021-01-01
- 设计字符串本地化的最佳方法 2022-01-01