এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম লিখতে যাচ্ছি যা একটি লাইনের অংশগুলির মিলনের দৈর্ঘ্য খুঁজে বের করে৷
আমাদের লাইন সেগমেন্টের শুরু এবং শেষ বিন্দু দেওয়া হয়েছে এবং আমাদের লাইনের অংশগুলির মিলনের দৈর্ঘ্য খুঁজে বের করতে হবে।
আমরা যে অ্যালগরিদমটি ব্যবহার করতে যাচ্ছি তাকে বলা হয় ক্লিস অ্যালগরিদম৷
৷আসুন সমস্যা সমাধানের পদক্ষেপগুলি দেখি৷
৷- সমস্ত সেগমেন্টের স্থানাঙ্ক সহ অ্যারে শুরু করুন।
- সেগমেন্ট অ্যারের দ্বিগুণ আকারের সাথে পয়েন্ট নামক একটি ভেক্টর শুরু করুন।
- সেগমেন্ট অ্যারের উপর পুনরাবৃত্তি করুন।
- বর্তমান সেগমেন্টের প্রথম পয়েন্ট এবং মিথ্যা দিয়ে ইনডেক্স i * 2 এ পয়েন্ট অ্যারের মান পূরণ করুন।
- বর্তমান সেগমেন্টের দ্বিতীয় বিন্দু দিয়ে i * 2 + 1 সূচকে পয়েন্ট অ্যারের মান পূরণ করুন এবং মিথ্যা।
- পয়েন্ট অ্যারে সাজান।
- একটি কাউন্টার ভেরিয়েবল দিয়ে পয়েন্ট অ্যারের উপর পুনরাবৃত্তি করুন।
- যদি কাউন্টারটি 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
উপসংহার
টিউটোরিয়ালে আপনার কোন প্রশ্ন থাকলে মন্তব্য বিভাগে উল্লেখ করুন।
