Description Link to heading

[452.minimum-number-of-arrows-to-burst-balloons]

Solution Link to heading

First, sort points array by x_start from smallest to largest, then we need analyze how many arrows we need.

  • if (points[i][0] > points[i - 1]), there is no common space between two balloons, we need to arrow, result++;
  • else, then there is common space between two balloons, we need a new arrow. How about the next balloon?
    • if (points[i + 1][0] > min(points[i - 1][1], points[i][1])), then we need new arrow; if not , we don’t need. So we can make points[i][1] = min(points[i - 1][1], points[i][1]).

Code Link to heading 

#include <algorithm>
#include <vector>
using std::sort;
using std::vector;
class Solution {
  private:
    static bool cmp(vector<int> &a, vector<int> &b) {
        return a[0] < b[0];
    }

  public:
    int findMinArrowShots(vector<vector<int>> &points) {
        int result = 1;
        sort(points.begin(), points.end(), cmp);
        for (int i = 1; i < points.size(); i++) {
            if (points[i - 1][1] < points[i][0])
                result++;
            else {
                points[i][1] = min(points[i][1], points[i - 1][1]);
            }
        }
        return result;
    }
};