C++ですべての区間の共通部分（交差）を求めるアルゴリズム

問題の概要

{L, R} という形式で表される N 個の区間があるとします。ここで、L は開始時刻、R は終了時刻を表します。このとき、与えられたすべての区間に共通して含まれる「交差（共通部分）」を求める必要があります。交差とは、すべての区間の内部に存在する区間のことであり、そのような区間が存在しない場合は -1 を返します。

例えば、区間が [{1, 6}, {2, 8}, {3, 10}, {5, 8}] である場合、出力される区間は {5, 6} となります。

解法のアプローチ

この問題は、以下の手順で効率的に解くことができます。

• 最初の区間を「最終的な交差区間」として初期化します。
• 2番目の区間以降について、順番に交差を求めていきます。ここで2つの場合が考えられます。
  • 区間 [L1, R1] と [L2, R2] の間に交差が存在しないのは、R1 < L2 または R2 < L1 が成り立つ場合のみです。この場合、答えは -1 となります。
  • 区間 [L1, R1] と [L2, R2] の間に交差が存在する場合、求める交差は {max(L1, L2), min(R1, R2)} となります。

つまり、各区間を処理しながら「左端の最大値」と「右端の最小値」を更新していくことで、すべての区間の共通部分が自然に求まります。

実装例（C++）

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

アルゴリズムの計算量

このアルゴリズムは、すべての区間を一度だけ走査すればよいため、時間計算量は O(N)、追加のメモリ使用量は O(1) と非常に効率的です。区間の数が多くても高速に動作するため、スケジュールの重複検出や時間帯の共通範囲の特定など、実用的な場面でも活用できます。