C++を使用して重複する間隔をマージします。

問題の説明

任意の順序の時間間隔のセットを指定して、重複するすべての間隔を1つにマージし、相互に排他的な間隔のみを持つべき結果を出力します

与えられた間隔のセットは{{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}