資料結構
網路
關係型資料庫管理系統 (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 次瀏覽
廣告