資料結構
網路
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 次瀏覽
廣告