Loại bỏ khoảng bao phủ trong C++

Cho danh sách khoảng intervals, loại bỏ tất cả khoảng bị bao phủ bởi khoảng khác. Khoảng [a,b) bị [c,d) bao phủ nếu c ≤ a và b ≤ d. Trả về số khoảng còn lại.

Ví dụ: [[1,4],[3,6],[2,8]] → Kết quả: 2. Khoảng [3,6] bị [1,4] và [2,8] bao phủ.

Giải thuật (Sắp xếp + Ngăn xếp)

1. Sắp xếp khoảng theo thời gian kết thúc tăng dần.
2. Ngăn xếp st lưu các khoảng không bị bao phủ.
3. Duyệt từng khoảng a[i]:
4. Nếu st rỗng hoặc a[i] không giao với đỉnh st, push a[i].
5. Ngược lại: temp = a[i], pop khỏi st while giao nhau, sau đó push temp.
6. Trả về kích thước st.

Ví dụ C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool intersect(vector<int>& a, vector<int>& b) {
        return (b[0] <= a[0] && b[1] >= a[1]) || (a[0] <= b[0] && a[1] >= b[1]);
    }
    static bool cmp(vector<int> a, vector<int> b) { return a[1] < b[1]; }
    int removeCoveredIntervals(vector<vector<int>>& a) {
        sort(a.begin(), a.end(), cmp);
        stack<vector<int>> st;
        for(int i = 0; i < a.size(); i++) {
            if(st.empty() || !intersect(a[i], st.top())) st.push(a[i]);
            else {
                vector<int> temp = a[i];
                while(!st.empty() && intersect(temp, st.top())) st.pop();
                st.push(temp);
            }
        }
        return st.size();
    }
};

int main() {
    vector<vector<int>> v = {{1,4},{3,6},{2,8}};
    Solution ob;
    cout << (ob.removeCoveredIntervals(v));
    return 0;
}

Đầu vào

[[1,4],[3,6],[2,8]]

Đầu ra

2