मान लीजिए हमारे पास अंतरालों की एक द्वि-आयामी सूची है जहां प्रत्येक अंतराल में दो मान [start, end] होते हैं। हमें जांचना है कि क्या कोई ऐसा अंतराल है जो दूसरे अंतराल को समाहित करता है।
उदाहरण के लिए, यदि इनपुट [[2,4], [5,11], [5,9], [10,10]] है, तो आउटपुट true होगा क्योंकि [5,11], [5,9] को समाहित करता है।
समाधान दृष्टिकोण
इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
- सरणी
vको सॉर्ट करें - एक 2D सरणी
retपरिभाषित करें vमें प्रत्येक अंतरालitके लिए:- यदि
retखाली है, तोitकोretके अंत में डालें - अन्यथा यदि
ret के अंतिम तत्व का पहला मान >= it[0], तोtrueलौटाएं - अन्यथा
itकोretके अंत में डालें
- यदि
falseलौटाएं
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;
}
इनपुट
{{2,4}, {5,11}, {5,9}, {10,10}}
आउटपुट
1