C++에서 모든 배너를 걸기 위해 필요한 최소 핀 수를 찾는 프로그램

<시간/>

[start, end] 형식의 간격 목록이 있다고 가정해 보겠습니다. 이 목록은 우리가 걸고자 하는 배너의 시작점과 끝점을 나타냅니다. 배너를 걸려면 하나 이상의 핀이 필요하며 하나의 핀은 배너를 두 번 이상 걸 수 있습니다. 모든 배너를 걸기 위해 필요한 가장 작은 핀 수를 찾아야 합니다.

따라서 입력이 간격 =[[2, 5],[5, 6],[8, 10],[10, 13]]과 같으면 출력은 2가 됩니다. 5와 10을 눌러 모든 배너를 걸 수 있습니다.

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

간격의 끝 값을 기준으로 배열 v 정렬
ret :=0
마지막 :=-inf
각 항목에 대해 v −
- 마지막>=시작이면 -
  - 다음 부분은 무시하고 다음 반복으로 건너뜁니다.
- (ret 1 증가)
- 마지막 :=끝
반환

예시(C++)

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   static bool cmp(vector<int>& a, vector<int>& b) {
      return a.back() < b.back();
   }
   int solve(vector<vector<int>>& v) {
      sort(v.begin(), v.end(), cmp);
      int ret = 0;
      int last = -1e8;
      for (auto& it : v) {
         if (last >= it[0]) {
            continue;
         }
         ret++;
         last = it[1];
      }
      return ret;
   }
};
int solve(vector<vector<int>>& intervals) {
   return (new Solution())->solve(intervals);
}
int main(){
   vector<vector<int>> v = {{2, 5},{5, 6},{8, 10},{10, 13}};
   cout << solve(v);
}

입력

{{2, 5},{5, 6},{8, 10},{10, 13}}