Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में गुब्बारे फोड़ने के लिए न्यूनतम तीर


मान लीजिए दो-आयामी स्थान में कुछ गोलाकार गुब्बारे फैले हैं। प्रत्येक गुब्बारे के लिए क्षैतिज व्यास के प्रारंभ और अंत निर्देशांक दिए गए हैं। एक तीर को x-अक्ष पर किसी बिंदु से लंबवत ऊपर दागा जा सकता है। एक गुब्बारा फट जाता है यदि तीर का x-निर्देशांक गुब्बारे के xstart और xend के बीच हो। हमें सभी गुब्बारों को फोड़ने के लिए आवश्यक न्यूनतम तीरों की संख्या ढूंढनी है।

उदाहरण: [[10,16],[2,8],[1,6],[7,12]] → आउटपुट 2 (x=6 पर तीर से [2,8] और [1,6] फटते हैं, x=11 पर तीर से बाकी)।

लालची एल्गोरिदम (अंत बिंदु द्वारा सॉर्ट)

  1. गुब्बारों को उनके अंत निर्देशांक (xend) के आधार पर सॉर्ट करें।
  2. currEnd = पहले गुब्बारे का अंत, count = 1।
  3. प्रत्येक गुब्बारे के लिए:
    • यदि गुब्बारे का प्रारंभ > currEnd, तो नया तीर चाहिए: count++, currEnd = इस गुब्बारे का अंत।
  4. count लौटाएँ।

C++ कार्यान्वयन

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a[1] < b[1];
    }
    
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), cmp);
        int n = points.size();
        if (!n) return 0;
        int currEnd = points[0][1];
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (currEnd < points[i][0]) {
                cnt++;
                currEnd = points[i][1];
            }
        }
        return cnt;
    }
};

int main() {
    vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
    Solution ob;
    cout << ob.findMinArrowShots(v); // 2
    return 0;
}

इनपुट

[[10,16],[2,8],[1,6],[7,12]]

आउटपुट

2
  1. - C++ में न्यूनतम पृष्ठों का आवंटन

    न्यूनतम पृष्ठों का आवंटन एक प्रोग्रामिंग समस्या है। आइए इस समस्या पर विस्तार से चर्चा करते हैं और देखते हैं कि इसका समाधान क्या हो सकता है। कथन आपको n विभिन्न पुस्तकों के पृष्ठों की संख्या दी गई है। साथ ही, m छात्र हैं जिन्हें पुस्तकें आवंटित की जानी हैं। पुस्तकें पृष्ठों की संख्या के आरोही क्रम में

  1. - C++ में वेरिएबल नंबर ऑफ आर्गुमेंट्स

    कभी-कभी, आप एक ऐसी स्थिति का सामना कर सकते हैं, जब आप एक ऐसा फंक्शन चाहते हैं, जो वेरिएबल नंबर ऑफ आर्गुमेंट्स ले सके, यानी, पैरामीटर्स, पूर्वनिर्धारित संख्या के पैरामीटर्स के बजाय। C/C++ प्रोग्रामिंग लैंग्वेज इस स्थिति के लिए एक समाधान प्रदान करती है और आपको एक ऐसा फंक्शन डिफाइन करने की अनुमति देती

  1. - C++ में CHAR_BIT

    CHAR_BIT क्या है? CHAR_BIT एक बाइट में बिट्स की संख्या दर्शाता है। <climits> या <limits.h> हेडर में परिभाषित। आमतौर पर 8 बिट्स प्रति बाइट होता है। C++ प्रोग्राम उदाहरण #include <bits/stdc++.h> using namespace std; int main() { int x = 28; int total_bits = CHAR_BIT * size