C++ 5 line O(N) time


  • 0
    // 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.

Log in to reply
 

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