数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚学
法律教程C++ 中的包含间隔
假设我们有一个包含多个区间的二维列表，其中每个区间包含两个值 [start, end]。我们需要找出是否存在包含另一个区间的区间。
因此，如果输入类似于 [[2,4],[5,11],[5,9],[10,10]]，则输出将为真，因为 [5,11] 包含 [5,9]。
为了解决这个问题，我们将按照以下步骤进行 −
对数组 v 进行排序
定义一个二维数组 ret
对于 v 中的每个区间 it −
如果 ret 为空，则 −
将其插入 ret 的末尾
否则，当 ret 的最后一个元素 >= it[0]，则 −
返回真
否则
将其插入 ret 的末尾
返回假
让我们看看以下实现，以获得更好的理解 −
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool static 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;
}
};
main() {
Solution ob;
vector<vector<int>> v = {{2,4},{5,11},{5,9},{10,10}};
cout << (ob.solve(v));
}输入
{{2,4},{5,11},{5,9},{10,10}}输出
1
更新于： 2020 年 9 月 2 日
346 次浏览
广告