Hợp nhất các khoảng chồng chéo bằng C ++.

Tuyên bố vấn đề

Đưa ra một tập hợp các khoảng thời gian theo thứ tự bất kỳ, hãy hợp nhất tất cả các khoảng chồng lên nhau thành một và xuất ra kết quả chỉ nên có các khoảng loại trừ lẫn nhau

Tập hợp khoảng thời gian đã cho là {{12, 14}, {11, 13}, {20, 22}, {21, 23}} thì

• Khoảng thời gian {12, 14} và {11, 13} chồng lên nhau do đó hợp nhất chúng thành {11, 14}

• Khoảng thời gian {20, 22} và {21, 23} chồng chéo với nhau do đó hợp nhất chúng thành {20, 23}

Thuật toán

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.

Ví dụ

#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;
}

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Merged intervals:
{20, 23} {11, 14}