C++ में सभी बैनर लटकाने के लिए आवश्यक न्यूनतम पिन की संख्या ढूंढने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास [शुरुआत, अंत] फॉर्म के अंतरालों की एक सूची है जो हमारे द्वारा लटकाए जाने वाले बैनरों के प्रारंभ और अंत बिंदुओं को दर्शाती है। एक बैनर लटकाने के लिए कम से कम एक पिन की आवश्यकता होती है, और एक पिन एक से अधिक बैनर लटका सकता है। हमें सभी बैनर लटकाने के लिए आवश्यक पिन की न्यूनतम संख्या ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है intervals = [[2, 5], [5, 6], [8, 10], [10, 13]], तो आउटपुट 2 होगा, क्योंकि हम पोजीशन 5 और 10 पर दो पिन लगाकर सभी बैनर लटका सकते हैं।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम लालची एल्गोरिदम का उपयोग करेंगे:

1. v ऐरे को अंतराल के अंत मानों के आधार पर सॉर्ट करें
2. ret := 0
3. last := -अनंत
4. v में प्रत्येक आइटम it के लिए:
   • यदि last >= it की शुरुआत, तो अगले इटरेशन पर जाएं
   • ret बढ़ाएं
   • last := it का अंत
5. ret वापस करें

उदाहरण

#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