Các khoảng không chồng lấn trong C++

Cho tập hợp các khoảng, tìm số khoảng tối thiểu cần xóa để các khoảng còn lại không chồng lấn. Ví dụ: [[1,2],[2,3],[3,4],[1,3]] → 1 (xóa [1,3]).

Giải thuật

• n := kích thước mảng; nếu n == 0 trả về 0.
• count := 1.
• Sắp xếp mảng theo thời gian kết thúc tăng dần.
• end := end của khoảng đầu tiên.
• Với i từ 1 đến n-1: nếu start của arr[i] ≥ end thì end = end của arr[i], count++.
• Trả về n - count.

Ví dụ mã C++

#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;
    }
};

Đầu vào

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

Đầu ra

2