मान लीजिए दो-आयामी स्थान में कुछ गोलाकार गुब्बारे फैले हैं। प्रत्येक गुब्बारे के लिए क्षैतिज व्यास के प्रारंभ और अंत निर्देशांक दिए गए हैं। एक तीर को x-अक्ष पर किसी बिंदु से लंबवत ऊपर दागा जा सकता है। एक गुब्बारा फट जाता है यदि तीर का x-निर्देशांक गुब्बारे के xstart और xend के बीच हो। हमें सभी गुब्बारों को फोड़ने के लिए आवश्यक न्यूनतम तीरों की संख्या ढूंढनी है।
उदाहरण: [[10,16],[2,8],[1,6],[7,12]] → आउटपुट 2 (x=6 पर तीर से [2,8] और [1,6] फटते हैं, x=11 पर तीर से बाकी)।
लालची एल्गोरिदम (अंत बिंदु द्वारा सॉर्ट)
- गुब्बारों को उनके अंत निर्देशांक (
xend) के आधार पर सॉर्ट करें। currEnd = पहले गुब्बारे का अंत,count = 1।- प्रत्येक गुब्बारे के लिए:
- यदि गुब्बारे का प्रारंभ
> currEnd, तो नया तीर चाहिए:count++,currEnd = इस गुब्बारे का अंत।
- यदि गुब्बारे का प्रारंभ
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