資料結構
網路
關係型資料庫管理系統
作業系統
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 次瀏覽
廣告