数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学C++ 实现 Klee 算法（计算线段并集长度）
在本教程中，我们将编写一个程序来查找线段并集的长度。
给定线段的起点和终点，我们需要找到线段并集的长度。
我们将使用的算法称为 Klee 算法。
让我们看看解决问题的步骤。
- 用所有线段的坐标初始化数组。
- 用两倍于线段数组大小初始化名为 points 的向量。
- 迭代线段数组。
- 用当前线段的第一个点和 false 填充 points 数组中索引 i * 2 的值。
- 用当前线段的第二个点和 false 填充 points 数组中索引 i * 2 + 1 的值。
- 对 points 数组进行排序。
- 使用计数器变量迭代 points 数组。
- 如果计数器大于 0，则将 i 和 i - 1 的第一个点添加到结果中。
- 如果存在第二个点则递减计数器，否则递增计数器。
- 返回结果。
示例
让我们看看代码。
#include<bits/stdc++.h>
using namespace std;
int segmentUnionLength(const vector<pair <int,int>> &segments) {
int n = segments.size();
vector<pair<int, bool>> points(n * 2);
for (int i = 0; i < n; i++) {
points[i*2] = make_pair(segments[i].first, false);
points[i*2 + 1] = make_pair(segments[i].second, true);
}
sort(points.begin(), points.end());
int result = 0, count = 0;
for (int i = 0; i < n * 2; i++){
if (count) {
result += points[i].first - points[i-1].first;
}
points[i].second ? count-- : count++;
}
return result;
}
int main() {
vector<pair<int,int>> segments;
segments.push_back(make_pair(1, 3));
segments.push_back(make_pair(2, 7));
segments.push_back(make_pair(6, 12));
segments.push_back(make_pair(13, 5));
cout << segmentUnionLength(segments) << endl;
return 0;
}输出
如果运行上面的代码，则会得到以下结果。
6
结论
如果您对本教程有任何疑问，请在评论部分提出。
更新于：2021年4月9日
496 次浏览
广告