C++で互いに素な区間の最大集合を求めるアルゴリズム

概要

N個の区間（インターバル）が与えられたとき、互いに素な（重ならない）区間の最大集合を見つけることが本記事の課題です。2つの区間 [i, j] と [k, l] は、共通の点を1つも持たない場合に「互いに素（disjoint）」であると定義されます。

例えば、区間が {{10, 20}, {23, 35}, {15, 21}, {37, 41}} である場合、重なりなく選択できる最大の組み合わせは以下の通りです。

{10, 20}
{23, 35}
{37, 41}

ここで注意したいのは、{15, 21} を含めることができないという点です。{15, 21} は {10, 20} と重なってしまうためです。

アルゴリズム（貪欲法）

この問題は「活動時間割り当て問題」としても知られており、貪欲法（Greedy Algorithm）によって効率的に解くことができます。手順は以下の通りです。

1. 各区間の終点を基準にして、すべての区間をソートします。
2. すべての区間を先頭から順に走査し、直前に採用した区間と重なっている場合は、終点がより小さい方の区間を採用します。終点が小さい区間を選ぶことで、その後に続く区間をできるだけ多く、重なりなく受け入れられるようになります。
3. この手順をすべての区間に対して繰り返し、条件を満たす区間を出力します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
bool sortFun(pair<int, int> &a, pair<int, int> &b){
    return (a.second < b.second);
}
void getMaxDisjointInterval(vector<pair<int, int>> intervals){
    sort(intervals.begin(), intervals.end(), sortFun);
    cout << "{" << intervals[0].first << ", " << intervals[0].second << "}\n";
    int r1 = intervals[0].second;
    for (int i = 1; i < intervals.size(); ++i) {
        int l1 = intervals[i].first;
        int r2 = intervals[i].second;
        if (l1 > r1) {
            cout << "{" << l1 << ", " << r2 << "}\n";
            r1 = r2;
        }
    }
}
int main(){
    int n = 4;
    vector<pair<int, int>> intervals = {
        {10, 20},
        {23, 35},
        {15, 21},
        {37, 41}
    };
    cout << "Max disjoint pairs are:\n";
    getMaxDisjointInterval(intervals);
    return 0;
}

コードのポイント

• sortFun 関数は、各 pair の2番目の要素（区間の終点）を比較することで、区間を終点順に並べ替えます。
• getMaxDisjointInterval 関数では、最初の区間を出力した後、変数 r1 に現在採用中の区間の終点を保持します。
• 以降の区間については、始点 l1 が r1 より大きい場合のみ出力し、r1 を更新していきます。これにより重なりを確実に回避できます。

出力結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Max disjoint pairs are:
{10, 20}
{23, 35}
{37, 41}

計算量について

このアルゴリズムの計算量は、区間のソートに O(N log N)、走査に O(N) かかるため、全体として O(N log N) となります。区間スケジューリング問題の中でも非常に効率的な解法であり、実務上のスケジュール最適化やリソース割り当ての問題にも応用できます。