Khoảng chứa nhau trong C++

Cho danh sách khoảng [start, end]. Kiểm tra có tồn tại khoảng nào chứa khoảng khác không.

Ví dụ: [[2,4],[5,11],[5,9],[10,10]] → true vì [5,11] chứa [5,9].

Giải thuật: Sắp xếp khoảng theo end tăng, nếu end bằng nhau thì start giảm. Duyệt, nếu start của khoảng hiện tại ≤ start của khoảng trước trong kết quả → có chứa nhau.

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] ? a[0] > b[0] : a[1] < b[1];
    }
    bool solve(vector<vector<int>>& v) {
        sort(v.begin(), v.end(), cmp);
        vector<vector<int>> ret;
        for (auto& it : v) {
            if (ret.empty()) ret.push_back(it);
            else if (ret.back()[0] >= it[0]) return true;
            else ret.push_back(it);
        }
        return false;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{2,4},{5,11},{5,9},{10,10}};
    cout << (ob.solve(v));
}

Đầu vào

{{2,4},{5,11},{5,9},{10,10}}

Đầu ra

1