C++에서 모든 간격의 교차점 찾기

{L, R} 형식의 N 간격이 있고 L이 시작 시간이고 R이 종료 시간이라고 가정합니다. 모든 구간의 교차점을 찾아야 합니다. 교차는 주어진 모든 간격 내에 있는 간격입니다. 해당 항목이 없으면 -1을 반환합니다. 예를 들어 간격이 [{1, 6}, {2, 8}, {3, 10}, {5, 8}인 경우 출력 간격은 {5, 6}

이 문제를 해결하기 위해 다음 단계를 따르십시오 -

• 첫 번째 간격이 마지막 간격이라고 생각하십시오.

• 두 번째 구간부터 교차로를 찾아보세요. 두 가지 경우가 있을 수 있습니다.

  • [L1, R1]과 [L2, R2] 사이에는 교차점이 존재하지 않습니다. R1 입니다.

  • [L1, R1]과 [L2, R2] 사이에 교차점이 없으며 필요한 교차점은 {max(L1, L2), min(R1, R2)}

    입니다.

예시

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

출력

{5, 6}