Tìm giao điểm của tất cả các khoảng trong C ++

Giả sử, chúng ta có N khoảng thời gian ở dạng {L, R}, L là thời gian bắt đầu và R là thời gian kết thúc. Chúng ta phải tìm giao điểm của tất cả các khoảng. Giao điểm là một khoảng nằm trong tất cả các khoảng đã cho. Nếu không tìm thấy như vậy, trả về -1. Ví dụ:nếu các khoảng như [{1, 6}, {2, 8}, {3, 10}, {5, 8}, thì Khoảng đầu ra là {5, 6}

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Coi khoảng đầu tiên là khoảng cuối cùng

• Bắt đầu từ khoảng thứ hai, hãy thử tìm kiếm giao lộ. Có thể có hai trường hợp

  • Không tồn tại sự giao nhau giữa [L1, R1] và [L2, R2] chỉ khi R1

  • Không tồn tại giao điểm giữa [L1, R1] và [L2, R2], khi đó giao điểm bắt buộc sẽ là {max (L1, L2), min (R1, R2)}

Ví dụ

#include<iostream>
#include<algorithm>
using namespace std;
class interval{
   public:
      int left, right;
};
void findIntersection(interval intervals[], int N) {
   int l = intervals[0].left;
   int r = intervals[0].right;
   for (int i = 1; i < N; i++) {
      if (intervals[i].left > r || intervals[i].right < l) {
         cout << -1;
         return;
      } else {
         l = max(l, intervals[i].left);
         r = min(r, intervals[i].right);
      }
   }
   cout << "{" << l << ", " << r << "}";
}
int main() {
   interval intervals[] = {{ 1, 6 }, { 2, 8 }, { 3, 10 }, { 5, 8 } };
   int N = sizeof(intervals) / sizeof(intervals[0]);
   findIntersection(intervals, N);
}

Đầu ra

{5, 6}