C++에서 풍선을 터뜨리기 위한 최소 화살표 수

2차원 공간에 몇 개의 구형 풍선이 펼쳐져 있다고 가정합니다. 각 풍선에는 수평 지름의 시작 좌표와 끝 좌표가 있습니다. 시작은 항상 끝보다 작습니다. 최대 104개의 풍선이 있을 것입니다. 하나의 화살표는 x축을 따라 다른 지점에서 정확히 수직으로 쏠 수 있습니다. xstart에서 xend까지의 위치가 xstart인 풍선은 xstart =x =xend인 경우 x를 향해 쏜 화살로 폭발합니다. 발사할 수 있는 화살의 수에는 제한이 없습니다. 한 번 발사된 화살은 계속 무한히 날아간다고 가정하자. 모든 풍선을 터뜨리기 위해 쏴야 하는 최소 화살 수를 찾아야 합니다. 따라서 입력이 [[10,16],[2,8], [1,6], [7,12]]와 같으면 출력은 2가 됩니다. 따라서 x =6에서 쏘면 [2,8] 및 [1,6]을 터뜨리고 x =11에서 다른 풍선을 터트려 나머지를 터트립니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 위치가 교차하는지 여부를 확인하기 위해 intersect()라는 메서드를 정의합니다.

• 모든 교차 풍선의 범위를 취한 후 범위를 조작하는 또 다른 방법 manage()

• 실제 방법은 풍선 위치를 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