मान लीजिए कि दो-आयामी अंतरिक्ष में फैले कुछ गोलाकार गुब्बारे हैं। प्रत्येक गुब्बारे के लिए, क्षैतिज व्यास के प्रारंभ और अंत निर्देशांक होते हैं। प्रारंभ हमेशा अंत से छोटा होता है। इसमें अधिकतम 104 गुब्बारे होंगे। एक तीर को एक्स-अक्ष के साथ विभिन्न बिंदुओं से बिल्कुल लंबवत रूप से शूट किया जा सकता है। एक गुब्बारा जिसकी स्थिति xstart से xend है, x पर एक तीर से फट जाता है यदि xstart =x =xend। शूट किए जा सकने वाले तीरों की संख्या की कोई सीमा नहीं है। मान लीजिए कि एक बार गोली मारने वाला तीर असीम रूप से ऊपर की ओर बढ़ता रहता है। हमें सभी गुब्बारों को फोड़ने के लिए कम से कम तीरों की संख्या ज्ञात करनी होगी। तो अगर इनपुट [[10,16], [2,8], [1,6], [7,12]] जैसा है, तो आउटपुट 2 होगा। तो अगर हम एक्स =6 से शूट करते हैं, तो यह [2,8] और [1,6] फटेंगे, और बाकी को फोड़ने के लिए x =11 से एक और गुब्बारा फोड़ेंगे।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
यह जाँचने के लिए कि स्थान प्रतिच्छेद कर रहे हैं या नहीं, प्रतिच्छेद () नामक एक विधि को परिभाषित करें
-
सभी प्रतिच्छेद करने वाले गुब्बारों की रेंज लेने के बाद रेंज में हेरफेर करने के लिए एक अन्य विधि मैनिपुलेट () करती है
-
वास्तविक विधि गुब्बारे की स्थिति को पॉज़ के रूप में ले रही है
-
अंतिम स्थिति के आधार पर पॉज़ ऐरे को सॉर्ट करें
-
n :=गुब्बारों की संख्या, यदि n 0 है, तो वापस 0
-
currEnd :=सोरिंग के बाद पोज़ की पहली प्रविष्टि की अंतिम स्थिति
-
सीएनटी:=1
-
मैं के लिए 1 से n - 1 की सीमा में
-
अगर currEnd
-
-
वापसी की संख्या
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool intersect(vector <int>& a, vector <int>& b){
return a[1] >= b[0];
}
static bool cmp(vector <int>& a, vector <int>& b){
return a[1] < b[1];
}
void manipulate(vector <int>& a, vector <int>& b){
a[0] = min(a[0], b[0]);
a[1] = max(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;
}
};
main(){
vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
Solution ob;
cout << (ob.findMinArrowShots(v));
} इनपुट
[[10,16],[2,8],[1,6],[7,12]]
आउटपुट
2