数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会学
时尚学
法律学使用 C++ 合并重叠区间。
问题陈述
给定一组时间区间（无序），将所有重叠的区间合并为一个，并输出结果，其中应仅包含互斥的区间
给定的区间集为 {{12, 14}, {11, 13}, {20, 22}, {21, 23}} 则
区间 {12, 14} 和 {11, 13} 相互重叠，因此将它们合并为 {11, 14}
区间 {20, 22} 和 {21, 23} 相互重叠，因此将它们合并为 {20, 23}
算法
1. Sort the intervals based on increasing order of starting time 2. Push the first interval on to a stack 3. For each interval perform below steps: 3.1. If the current interval does not overlap with the top of the stack, push it. 3.2. If the current interval overlaps with top of the stack and ending time of current interval is more than that of top of stack, update stack top with the ending time of current interval. 4. Finally, stack contains the merged intervals.
示例
#include <iostream>
#include <algorithm>
#include <stack>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct interval{
int start;
int end;
};
bool compareInterval(interval i1, interval i2){
return (i1.start < i2.start);
}
void mergeOverlappingIntervals(interval *arr, int n){
if (n <= 0) {
return;
}
stack<interval> s;
sort(arr, arr + n, compareInterval);
s.push(arr[0]);
for (int i = 1; i < n; ++i) {
interval top = s.top();
if (top.end < arr[i].start) {
s.push(arr[i]);
} else if(top.end < arr[i].end) {
top.end = arr[i].end;
s.pop();
s.push(top);
}
}
cout << "Merged intervals: " << endl;
while (!s.empty()) {
interval i = s.top();
cout << "{" << i.start << ", " << i.end << "}" << " ";
s.pop();
}
cout << endl;
}
int main(){
interval arr[] = {{12, 14}, {11, 13}, {20, 22}, {21, 23}};
mergeOverlappingIntervals(arr, SIZE(arr));
return 0;
}输出
当你编译和执行上述程序时，它将生成以下输出 -
Merged intervals:
{20, 23} {11, 14}
更新时间：2019 年 10 月 31 日
530 次浏览
广告