C++で区間の集合の中に重なり合う区間が存在するかどうかを判定する方法

あるイベントの開始時刻と終了時刻を表す値のペア（time1, time2）から構成される区間の集合が与えられたとします。ここでの課題は、この集合の中に他の区間と重なり合っている区間が存在するかどうかを確認することです。重なりが1つでも見つかれば True を返し、まったく重なりがなければ False を返します。

例えば、入力が [(4,7), (5,11), (7,11), (5,8)] のような場合、出力は True になります。これは複数の区間が互いに重なっているためです。

解決のアプローチ

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

• まず、入力リスト inputArr を開始時刻（time1）を基準にソートします。
• インデックス 1 から inputArr のサイズまでループ処理を行います。
  • もし inputArr[i - 1].time2 > inputArr[i].time1 が成り立つ場合、前の区間の終了時刻が次の区間の開始時刻より後であることを意味するため、
    • True を返します。
  • ループが完了しても重なりが見つからなければ、False を返します。

ソート後は隣接する区間同士だけを比較すればよいため、全体の計算量は O(n log n)（ソート部分が支配的）となり、非常に効率的です。

実装例

それでは、実際のC++コードを見て理解を深めましょう。

#include <bits/stdc++.h>
using namespace std;
class IntervalClass {
public:
    int time1, time2;
};
bool compare(IntervalClass inst1, IntervalClass inst2){
    return (inst1.time1 < inst2.time1) ? true : false;
}
bool solve(vector<IntervalClass> &inputArr){
    int size = inputArr.size();
    sort(inputArr.begin(), inputArr.end(), compare);
    for (int i = 1; i < size; i++)
        if (inputArr[i - 1].time2 > inputArr[i].time1)
            return true;
    return false;
}
int main(){
    vector<IntervalClass> inputArr = {{4,7},{5,11},{7,11},{5,8}};
    cout << solve(inputArr);
}

入力

{{4,7},{5,11},{7,11},{5,8}}

出力

1

コードの解説

このコードでは、IntervalClass クラスで各区間の開始時刻（time1）と終了時刻（time2）を保持しています。compare 関数は、区間を開始時刻順に並べるための比較関数です。

solve 関数では、まず sort によって全ての区間を開始時刻順に並べ替えます。その後、隣接する区間を順番に比較し、「前の区間の終了時刻が次の区間の開始時刻を超えている」場合は重なりがあると判断して true を返します。

上記の例では、例えば (4,7) と (5,11) のように、ソート後に隣接する区間が重なっているため、出力は 1（True）となります。もし全ての区間が互いに離れていれば、出力は 0（False）になります。