อัลกอริทึมของ Klee (ความยาวของยูเนียนของส่วนเส้น) ใน C++

ในบทช่วยสอนนี้ เราจะเขียนโปรแกรมเพื่อหาความยาวของยูเนียนของส่วนเส้นบนเส้นตรง

เราได้รับจุดเริ่มต้นและจุดสิ้นสุดของส่วนเส้น และต้องการหาความยาวของยูเนียนของส่วนเส้นเหล่านั้น

อัลกอริทึมที่เราจะใช้เรียกว่า Klee's Algorithm

ขั้นตอนการแก้ปัญหา

กำหนดค่าเริ่มต้นของอาร์เรย์ด้วยพิกัดของทุกส่วนเส้น
กำหนดเวกเตอร์ชื่อ points ขนาดสองเท่าของอาร์เรย์ส่วนเส้น
วนลูปผ่านอาร์เรย์ส่วนเส้น
- เติมค่าของอาร์เรย์ points ที่ดัชนี i * 2 ด้วยจุดแรกของส่วนเส้นปัจจุบันและค่า false
- เติมค่าของอาร์เรย์ points ที่ดัชนี i * 2 + 1 ด้วยจุดที่สองของส่วนเส้นปัจจุบันและค่า true
เรียงลำดับอาร์เรย์ points
วนลูปผ่านอาร์เรย์ points พร้อมตัวนับ counter
- ถ้า counter มากกว่า 0 ให้บวกความต่างของจุดแรกของ i และ i - 1 เข้าไปในผลลัพธ์
- ลด counter ถ้าเป็นจุดที่สอง มิฉะนั้นเพิ่ม counter
คืนค่าผลลัพธ์

ตัวอย่างโค้ด

#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; 
}

ผลลัพธ์

หากรันโค้ดด้านบน จะได้ผลลัพธ์ดังนี้:

สรุป

หากมีข้อสงสัยเกี่ยวกับบทช่วยสอนนี้ สามารถถามได้ในส่วนความคิดเห็น