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

Giả sử có một tập hợp các khoảng thời gian; ta phải tìm số lượng khoảng thời gian tối thiểu cần xóa để các khoảng còn lại không chồng chéo. Vì vậy nếu các khoảng là [[8,10],[3,5],[6,9]], thì đầu ra sẽ là 1, vì ta phải xóa [6,9] để các khoảng còn lại không chồng chéo.

Để giải quyết, ta làm theo các bước sau:

• n := kích thước mảng
• nếu n bằng 0, trả về 0
• count := 1
• sắp xếp mảng theo thời gian kết thúc của khoảng
• end := thời gian kết thúc của khoảng đầu tiên
• với i từ 1 đến n-1
  • nếu thời gian bắt đầu arr[i] >= end, thì end := thời gian kết thúc arr[i], tăng count 1
• trả về n - count

Hãy xem 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;
    }
};

int main() {
    vector<vector<int>> v = {{8,10},{3,5},{6,9}};
    Solution ob;
    cout << (ob.eraseOverlapIntervals(v));
    return 0;
}

Đầu vào

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

Đầu ra

1