数据结构
网络
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 次浏览
广告