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}