Loại bỏ khoảng trong C++

Cho danh sách khoảng không giao nhau, đã sắp xếp, mỗi khoảng [a, b] đại diện tập {x | a ≤ x < b}. Loại bỏ giao giữa các khoảng và khoảng toBeRemoved. Trả về danh sách khoảng sau khi loại bỏ, đã sắp xếp.

Ví dụ: [[0,2], [3,4], [5,7]], toBeRemoved = [1,6] → Kết quả: [[0,1], [6,7]].

Giải thuật

1. Hàm manipulate2(ans, y) tách khoảng cuối của ans bằng y.
2. Duyệt từng khoảng in[i], thêm vào ans.
3. Kiểm tra giao với toBeRemoved: nếu giao, gọi manipulate2.
4. Trả về ans.

Ví dụ C++

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

void print_vector(vector<vector<auto>> v) {
    cout << "[";
    for(int i = 0; i < v.size(); i++) {
        cout << "[";
        for(int j = 0; j < v[i].size(); j++) cout << v[i][j] << ", ";
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    bool isIntersect(vector<int> a, vector<int> b) {
        return max(a[0], a[1]) >= min(b[0], b[1]);
    }
    void manipulate2(vector<vector<int>>& a, vector<int> y) {
        vector<int> x = a.back(); a.pop_back();
        vector<int> z = x;
        x[0] = y[1]; z[1] = y[0];
        if(z[0] < z[1]) a.push_back(z);
        if(x[0] < x[1]) a.push_back(x);
    }
    vector<vector<int>> removeInterval(vector<vector<int>>& in, vector<int>& t) {
        vector<vector<int>> ans;
        int n = in.size();
        for(int i = 0; i < n; i++) {
            ans.push_back(in[i]);
            vector<int> a = ans.back(), b = t;
            if(a[0] > b[0]) swap(a, b);
            if(isIntersect(a, b)) manipulate2(ans, t);
        }
        return ans;
    }
};

int main() {
    vector<int> v2 = {1,6};
    vector<vector<int>> v1 = {{0,2},{3,4},{5,7}};
    Solution ob;
    print_vector(ob.removeInterval(v1, v2));
    return 0;
}

Đầu vào

[[0,2],[3,4],[5,7]] [1,6]

Đầu ra

[[0, 1, ],[6, 7, ],]