मान लीजिए कि हमारे पास फॉर्म के अंतराल की एक सूची है [प्रारंभ, अंत] यह उन बैनरों के प्रारंभ और अंत बिंदुओं का प्रतिनिधित्व कर रहा है जिन्हें हम लटकाना चाहते हैं। एक बैनर को टांगने के लिए कम से कम एक पिन की आवश्यकता होती है, और एक पिन एक से अधिक बार बैनर लटका सकता है। हमें सभी बैनरों को टांगने के लिए आवश्यक पिनों की न्यूनतम संख्या ज्ञात करनी होगी।
इसलिए, यदि इनपुट अंतराल की तरह है =[[2, 5], [5, 6], [8, 10], [10, 13]], तो आउटपुट 2 होगा, क्योंकि हम दो पिनों को स्थिति में रख सकते हैं। 5 और 10 सभी बैनर टांगने के लिए।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- अंतराल के अंतिम मूल्यों के आधार पर सरणी v को क्रमबद्ध करें
- रिट:=0
- अंतिम:=-इन्फ़
- प्रत्येक आइटम के लिए यह 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