ধরুন আমাদের কাছে ফর্মের অন্তর্বর্তীগুলির একটি তালিকা রয়েছে [শুরু, শেষ] এটি ব্যানারগুলির শুরু এবং শেষ পয়েন্টগুলিকে উপস্থাপন করে যা আমরা ঝুলতে চাই৷ একটি ব্যানার ঝুলানোর জন্য কমপক্ষে একটি পিন প্রয়োজন এবং একটি পিন একাধিকবার ব্যানার ঝুলিয়ে দিতে পারে। আমাদের সমস্ত ব্যানার ঝুলানোর জন্য প্রয়োজনীয় ক্ষুদ্রতম সংখ্যক পিনের সন্ধান করতে হবে৷
সুতরাং, যদি ইনপুটটি অন্তরের মত হয় =[[2, 5],[5, 6],[8, 10],[10, 13]], তাহলে আউটপুট হবে 2, যেমন আমরা অবস্থানে দুটি পিন রাখতে পারি। 5 এবং 10 সব ব্যানার টাঙানোর জন্য।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ব্যবধানের শেষ মানের উপর ভিত্তি করে অ্যারে v সাজান
- ret :=0
- শেষ :=-inf
- প্রতিটি আইটেমের জন্য এটি v −
- যদি শেষ হয়>=এর শুরু, তারপর −
- নিম্নলিখিত অংশ উপেক্ষা করুন, পরবর্তী পুনরাবৃত্তিতে যান
- (রেট 1 দ্বারা বৃদ্ধি করুন)
- শেষ :=এর শেষ
- যদি শেষ হয়>=এর শুরু, তারপর −
- রিটার্ন রিটার্ন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a.back() < b.back();
}
int solve(vector<vector<int>>& v) {
sort(v.begin(), v.end(), cmp);
int ret = 0;
int last = -1e8;
for (auto& it : v) {
if (last >= it[0]) {
continue;
}
ret++;
last = it[1];
}
return ret;
}
};
int solve(vector<vector<int>>& intervals) {
return (new Solution())->solve(intervals);
}
int main(){
vector<vector<int>> v = {{2, 5},{5, 6},{8, 10},{10, 13}};
cout << solve(v);
} ইনপুট
{{2, 5},{5, 6},{8, 10},{10, 13}} আউটপুট
2
