5-line C++ O(NlogN) concise solution with clean explanation

  • 0

    Key observation: any balloons with common range could be burst using a single arrow, so the problem is simply to ask how many disjoint common ranges formed by given balloons?

    Sort all balloons { Bi=1:N } by left edge x-coordinates. Note that if balloon subset { Bi } has a non-empty common range, clearly, we have

    • common range [L, R] = [maxi Bi.left, mini Bi.right].

    The position of current balloon Bcur v.s. last common range is either

    • intersecting, i.e., Bcur.left ≤ R, which means no addition arrow needed and we update to shrink the common range,
    • or disjoint, which means we discard the last common range since current balloon becomes the new common range, and we need a new arrow to burst it.
        int findMinArrowShots(vector<pair<int, int>>& points) {
          sort(points.begin(), points.end(), [](pair<int, int>& a, pair<int, int>& b){return a.first<b.first;});
          int res = 1; pair<int, int> common(INT_MIN, INT_MAX);
          for (auto& p:points)
            common = (p.first > common.second)? (++res,p) : make_pair(p.first, min(common.second, p.second));   
          return points.empty()? 0 : res;

Log in to reply

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