Contained Interval in C++: ตรวจสอบว่ามี Interval ที่ครอบคลุมอีก Interval หนึ่งหรือไม่

กำหนดรายการ intervals [start, end] ตรวจสอบว่ามี interval ไหนที่ "ครอบคลุม" interval อีกตัวหนึ่ง (คือ start ≤ other.start และ end ≥ other.end)

ตัวอย่าง: [[2,4],[5,11],[5,9],[10,10]] → true ([5,11] ครอบคลุม [5,9])

วิธีแก้ปัญหา

1. เรียง intervals โดย end ขึ้น, ถ้า end เท่ากัน เรียง start ลง
2. วนลูปเก็บ intervals ที่ "ไม่ถูกครอบคลุม" ไว้ใน ret
3. ถ้า interval ปัจจุบันมี start ≤ ret.back().start แสดงว่าถูกครอบคลุม → คืน true

ตัวอย่างโค้ด 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] ? 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);
}

Input

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

Output

1