C++でバルーンをバーストするための矢印の最小数

2次元空間に広がる球形の風船がほとんどないとします。バルーンごとに、水平方向の直径の開始座標と終了座標があります。開始は常に終了よりも小さくなります。最大104個の風船があります。 1つの矢印は、x軸に沿ったさまざまなポイントから正確に垂直に発射できます。 xstart =x =xendの場合、位置がxstartからxendのバルーンは、xで発射された矢印によって破裂します。発射できる矢の数に制限はありません。一度撃たれた矢が無限に上に移動し続けると仮定します。すべての風船を破裂させるために撃たなければならない矢の最小数を見つけなければなりません。したがって、入力が[[10,16]、[2,8]、[1,6]、[7,12]]の場合、出力は2になります。したがって、x =6から撮影すると、次のようになります。 [2,8]と[1,6]をバーストし、x=11から別のバルーンをバーストして残りをバーストします。

これを解決するには、次の手順に従います-

• 位置が交差しているかどうかを確認するためにintersect（）というメソッドを定義します

• 交差するすべてのバルーンの範囲を取得した後、範囲を操作する別のメソッドmanipulate（）

• 実際の方法は、バルーンの位置をposとして取得することです

• 終了位置に基づいてpos配列を並べ替えます

• n：=バルーンの数、nが0の場合、0を返します

• currEnd：=痛んだ後のposの最初のエントリの終了位置

• cnt：=1

• 1からn–1の範囲のiの場合

  • currEnd の終了位置

• 返品数

理解を深めるために、次の実装を見てみましょう

例

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool intersect(vector <int>& a, vector <int>& b){
      return a[1] >= b[0];
   }
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   void manipulate(vector <int>& a, vector <int>& b){
      a[0] = min(a[0], b[0]);
      a[1] = max(a[1], b[1]);
   }
   int findMinArrowShots(vector<vector<int>>& points) {
      sort(points.begin(), points.end(), cmp);
      int n = points.size();
      if(!n) return 0;
      int currEnd = points[0][1];
      int cnt = 1;
      for(int i = 1; i < n; i++){
         if(currEnd < points[i][0]){
            cnt++;
            currEnd = points[i][1];
         }
      }
      return cnt;
   }
};
main(){
   vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
   Solution ob;
   cout << (ob.findMinArrowShots(v));
}

入力

[[10,16],[2,8],[1,6],[7,12]]

出力

2