C++에서 제거할 최적의 간격을 찾는 프로그램

<시간/>

잠재적으로 겹칠 수 있는 간격 목록(포함)이 있다고 가정합니다. 이제 하나의 간격을 삭제한 다음 나머지 간격을 병합하고 남은 간격의 수를 계산하는 작업이 있다고 가정합니다. 제거 후 가능한 남은 간격의 최대 수를 찾아야 합니다.

따라서 입력이 간격 =[ [5, 8], [6, 7], [7, 10], [9, 11]]과 같으면 출력은 2가 됩니다. 이는 -

간격 [5, 8]을 삭제하면 병합으로 [6, 11]이 됩니다.
간격 [6, 7]을 삭제하면 병합으로 [5, 11]이 됩니다.
간격 [7, 10]을 삭제하면 병합으로 [5, 8], [9, 11]이 됩니다.
간격 [9, 11]을 삭제하면 병합으로 [5, 10]이 됩니다.

따라서 [7, 10]을 제거하는 것이 좋습니다.

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

숫자 쌍의 배열 메모 정의,
countIntervals() 함수를 정의합니다. 이것은 하나의 2D 배열 간격, i, 끝이 필요합니다.
- i가 간격의 크기와 같으면 -
  - 0 반환
- memo[i].first_element 이면
  - -무한대를 반환합니다.
- memo[i].first_element가 end와 같으면 -
  - 메모[i]의 두 번째 요소 반환
- end <간격[i, 0]이면 -
  - 메모[i] :=메모[i]의 끝과 첫째의 최소값, 1 + countIntervals(intervals, i + 1, interval[i, 1])
  - 메모[i]의 두 번째 요소 반환
- memo[i] :=memo[i] 및 countIntervals(intervals, i + 1, 간격[I, 1] 및 end의 최대값)의 끝과 첫 번째 요소의 최소값
- 메모[i]의 두 번째 값 반환
주요 방법에서 다음을 수행하십시오 -
- 간격 크기로 배열 메모 크기 조정
- 배열 간격 정렬
- 개수:=0, 결과:=0, 끝:=− 1
- 어레이 온도 정의
- for i :=0 ~ i <간격 크기, 업데이트(i 1 증가), 수행 -
  - 결과 :=결과 및 개수의 최대값 + countIntervals(intervals, i + 1,end)
  - end <간격[i, 0]이면 -
    - (1씩 증가)
  - 끝 :=끝과 간격의 최대값[i, 1]
- 반환 결과

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

예시

#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> memo;
int countIntervals(vector<vector<int>>& intervals, int i, int end) {
   if (i == intervals.size()) return 0;
   if (memo[i].first < end)
   return INT_MIN;
   if (memo[i].first == end)
   return memo[i].second;
   if (end < intervals[i][0]) {
      memo[i] = {min(end, memo[i].first), 1 +
      countIntervals(intervals, i + 1, intervals[i][1])};
      return memo[i].second;
   }
   memo[i] = {min(end, memo[i].first),
   countIntervals(intervals, i + 1, max(intervals[i][1],
   end))};
   return memo[i].second;
}
int solve(vector<vector<int>>& intervals) {
   memo.clear();
   memo.resize(intervals.size(), {INT_MAX, −1});
   sort(intervals.begin(), intervals.end());
   int count = 0, result = 0, end = −1;
   vector<int> temp;
   for (int i = 0; i < intervals.size(); i++) {
      result = max(result, count + countIntervals(intervals, i + 1,
      end));
      if (end < intervals[i][0])
         count++;
      end = max(end, intervals[i][1]);
   }
   return result;
}
int main(){
   vector<vector<int>> v = {{5, 8}, {6, 7}, {7, 10}, {9, 11}};
   cout<<solve(v);
}

입력

{{5, 8}, {6, 7}, {7, 10}, {9, 11}}