使用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}