Khoảng không 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 mà chúng ta cần 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à [[1,2], [2,3], [3,4], [1,3]], thì đầu ra sẽ là 1, vì chúng ta phải loại bỏ [1,3] để tạo tất cả những thứ khác đều không chồng chéo.

Để 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
đếm:=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 - số lượng

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 = {{1,2},{1,2},{1,2}};
   Solution ob;
   cout << (ob.eraseOverlapIntervals(v));
}

Đầu vào

[[1,2],[1,2],[1,2]]

Khoảng không chồng chéo trong C ++

Ví dụ

Đầu vào

Đầu ra