इस ट्यूटोरियल में, हम एक ऐसा प्रोग्राम लिखेंगे जो रेखा के खंडों के संघ की लंबाई ढूंढता है।
हमें रेखा खंड के प्रारंभिक और अंतिम बिंदु दिए गए हैं और हमें रेखा के खंडों के संघ की लंबाई ज्ञात करनी है।
हम जिस एल्गोरिदम का उपयोग करने जा रहे हैं उसे क्ली का एल्गोरिदम कहा जाता है।
आइए इस समस्या को हल करने के चरण देखते हैं।
- सभी खंडों के निर्देशांकों के साथ सरणी इनिशियलाइज़ करें।
- खंडों की सरणी के दोगुने आकार का एक वेक्टर पॉइंट्स इनिशियलाइज़ करें।
- खंडों की सरणी पर पुनरावृति करें।
- पॉइंट्स सरणी में इंडेक्स i * 2 पर वर्तमान खंड का पहला बिंदु और false भरें।
- पॉइंट्स सरणी में इंडेक्स i * 2 + 1 पर वर्तमान खंड का दूसरा बिंदु और true भरें।
- पॉइंट्स सरणी को सॉर्ट करें।
- एक काउंटर वेरिएबल के साथ पॉइंट्स सरणी पर पुनरावृति करें।
- यदि काउंटर 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
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उन्हें कमेंट सेक्शन में लिखें।
