C++-এ কন্টেইনড ইন্টারভাল: একটি ইন্টারভাল অন্যটি ধারণ করছে কিনা

ইন্টারভালের একটি তালিকা দেওয়া আছে। কোনো একটি ইন্টারভাল অন্য একটি ইন্টারভালকে সম্পূর্ণ ধারণ করছে কিনা তা যাচাই করুন।

উদাহরণ

ইনপুট: [[2,4], [5,11], [5,9], [10,10]]

আউটপুট: true

কারণ: [5,11] ইন্টারভালটি [5,9]-কে ধারণ করছে।

অ্যালগরিদম (সর্টিং + ট্র্যাকিং)

1. ইন্টারভালগুলোকে এন্ড পয়েন্ট অনুযায়ী সর্ট করুন। টাই হলে স্টার্ট পয়েন্ট বড়টি আগে।
2. ট্রাভার্স करते সময় সর্বনিম্ন স্টার্ট পয়েন্ট ট্র্যাক করুন।
3. যদি বর্তমান ইন্টারভালের স্টার্ট ≤ ট্র্যাককৃত মিনিমাম স্টার্ট হয়, তবে কন্টেইনমেন্ট আছে।

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);
    return 0;
}

কেন এটি কাজ করে?

এন্ড পয়েন্ট অনুযায়ী সর্ট করলে, যদি কোনো ইন্টারভাল আগের ইন্টারভালের মধ্যে পড়ে, তবে তার স্টার্ট পয়েন্ট আগের ইন্টারভালের স্টার্ট পয়েন্ট থেকে বড় বা সমান হবে।