C++ですべての間隔の交差を検索

{L、R}の形式でN個の間隔があり、Lが開始時刻、Rが終了時刻であるとします。すべての区間の交点を見つける必要があります。交点は、指定されたすべての区間内にある区間です。そのようなものが見つからない場合は、-1を返します。たとえば、間隔が[{1、6}、{2、8}、{3、10}、{5、8}の場合、出力間隔は{5、6}

この問題を解決するために、次の手順に従います-

• 最初の間隔が最後の間隔であると考えてください

• 2番目の間隔から始めて、交差点を検索してみてください。 2つのケースが存在する可能性があります

  • [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}