資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法律學用 C++ 查詢所有區間交集
假設我們有 N 個區間，形式為 {L, R}，L 為開始時間，R 為結束時間。我們必須求出所有區間的交集。交集是一個區間，它位於所有給定區間的內部。如果找不到，則返回 -1。例如，如果區間類似於 [{1, 6}, {2, 8}, {3, 10}, {5, 8}, 輸出區間為 {5, 6}
為了解決這個問題，我們將遵循以下步驟：
將第一個區間視為最終區間
從第二個區間開始，嘗試查詢交集。可能有兩種情況
如果 R1 < L2 或 R2 < L1，則 [L1, R1] 和 [L2, R2] 之間不存在交集，在這種情況下，答案為 0
如果 [L1, R1] 和 [L2, R2] 之間不存在交集，則所需的交集為 {max(L1, L2), min(R1, R2)}
示例
#include<iostream>
#include<algorithm>
using namespace std;
class interval{
public:
int left, right;
};
void findIntersection(interval intervals[], int N) {
int l = intervals[0].left;
int r = intervals[0].right;
for (int i = 1; i < N; i++) {
if (intervals[i].left > r || intervals[i].right < l) {
cout << -1;
return;
} else {
l = max(l, intervals[i].left);
r = min(r, intervals[i].right);
}
}
cout << "{" << l << ", " << r << "}";
}
int main() {
interval intervals[] = {{ 1, 6 }, { 2, 8 }, { 3, 10 }, { 5, 8 } };
int N = sizeof(intervals) / sizeof(intervals[0]);
findIntersection(intervals, N);
}輸出
{5, 6}
更新於:2019 年 12 月 19 日
738 次瀏覽
廣告