Chương trình tìm số lượng khoảng thời gian tối thiểu cần loại bỏ để loại bỏ chồng chéo trong C ++

Giả sử chúng ta có một tập hợp các khoảng; chúng ta phải tìm số khoảng tối thiểu cần được loại bỏ để làm cho các khoảng còn lại không trùng lặp. Vì vậy, nếu các khoảng là [[8,10], [3,5], [6,9]], thì đầu ra sẽ là 1, vì chúng ta phải loại bỏ [6,9] để làm cho tất cả các khoảng khác không chồng lên nhau .

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của mảng
• nếu n là 0, thì trả về 0
• số lượng:=1
• sắp xếp mảng dựa trên thời gian kết thúc của các khoảng thời gian
• end:=ngày kết thúc của khoảng thời gian đầu tiên
• cho tôi trong phạm vi từ 1 đến n - 1
  • nếu thời gian bắt đầu của arr [i]> =end, thì
    • end:=thời gian kết thúc của arr [i]
    • tăng số lượng lên 1
• return n - count

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   static bool cmp(vector <int>& a, vector <int>& b){
      return a[1] < b[1];
   }
   int eraseOverlapIntervals(vector<vector<int>>& arr) {
      int n = arr.size();
      if(!n)return 0;
         int cnt = 1;
         sort(arr.begin(), arr.end(), cmp);
         int end = arr[0][1];
         for(int i = 1; i < n; i++){
            if(arr[i][0] >= end){
               end = arr[i][1];
               cnt++;
         }
      }
      return n - cnt;
   }
};
main(){
   vector<vector<int>>
   v = {{8,10},{3,5},{6,9}};
   Solution ob;
   cout << (ob.eraseOverlapIntervals(v));
}

Đầu vào

{{8,10},{3,5},{6,9}}

Đầu ra

1