# C++ 5 line O(N) time

• ``````// OJ: https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons
// Auther: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
int findMinArrowShots(vector<pair<int, int>>& points) {
sort(points.begin(), points.end());
int cnt = 0, right = INT_MAX;
for (int i = 0; i < points.size(); ++cnt, right = INT_MAX)
for (; i < points.size() && right >= points[i].first; right = min(right, points[i++].second));
return cnt;
}
};
``````

Actually this is just for fun. It's compressed version of the following code (8 lines).

``````class Solution {
public:
int findMinArrowShots(vector<pair<int, int>>& points) {
sort(points.begin(), points.end());
int cnt = 0;
for (int i = 0; i < points.size(); ++cnt) {
int right = INT_MAX;
while (i < points.size() && right >= points[i].first)
right = min(right, points[i++].second);
}
return cnt;
}
};
``````

The idea behind is:

• Sort the points in ascending order of `Xstart`
• Keep `right` as the right bound of current interval, and `right = min(right, points[i].second)` to make the bound tighter.
• As long as the current ballon's `Xstart` is smaller or equal to `right`, this point can be bursted with previous ballons; otherwise, open up a new interval.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.