Problem Description
- Sort the bullons by their ending points
- Each time we shoot an arrow aiming at the smallest ending point and remove all the bullons that are bursted by this arrow
- Continue to do step 2 until all bullons are bursted
bool mycompare(pair<int,int> p1, pair<int,int> p2) {
return p1.second < p2.second || (p1.second == p2.second && p1.first < p2.first);
}
class Solution {
public:
int findMinArrowShots(vector<pair<int, int>>& points) {
sort(points.begin(), points.end(), mycompare);
int Count = 0;
while (!points.empty()) {
int CurrentArrow = points.front().second;
//cout << "CurrentArrow = " << CurrentArrow << endl;
Count++;
for (int i = 0; i < points.size(); i++) {
if (CurrentArrow >= points[i].first && CurrentArrow <= points[i].second) {
//cout << "i = " << i << endl;
//cout << "points[i].first = " << points[i].first << " points[i].second = " << points[i].second << endl;
points.erase(points.begin() + i);
i = -1;
}
}
}
return Count;
}
};
