C++で重複する区間をマージする方法【スタックを使った実装例】

問題の概要

任意の順序で与えられた時間区間（インターバル）の集合から、重なり合うすべての区間を1つに統合し、互いに重複しない区間だけを出力するのがこの問題の目的です。

たとえば、区間の集合 {{12, 14}, {11, 13}, {20, 22}, {21, 23}} が与えられた場合、次のように処理されます。

• {12, 14} と {11, 13} は互いに重なっているため、{11, 14} にマージされます。

• {20, 22} と {21, 23} も互いに重なっているため、{20, 23} にマージされます。

その結果、最終的な出力は {11, 14} と {20, 23} の2つの区間になります。

アルゴリズム

この問題は「開始時刻でソート」して「スタック」を活用することで効率的に解けます。手順は以下の通りです。

1. 区間を開始時刻の昇順にソートする
2. 最初の区間をスタックにプッシュする
3. 残りの各区間について以下を繰り返す：
    3.1. 現在の区間がスタックの先頭の区間と重ならない場合、
         現在の区間をスタックにプッシュする。
    3.2. 現在の区間がスタックの先頭と重なり、かつ現在の区間の
         終了時刻が先頭の区間より大きい場合は、スタックの先頭の
         終了時刻を現在の区間の終了時刻に更新する。
4. 最終的に、スタックにはマージ済みの区間が格納されている。

C++での実装例

以下は、上記のアルゴリズムをC++で実装したサンプルコードです。

#include <iostream>
#include <algorithm>
#include <stack>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
struct interval{
    int start;
    int end;
};
bool compareInterval(interval i1, interval i2){
    return (i1.start < i2.start);
}
void mergeOverlappingIntervals(interval *arr, int n){
    if (n <= 0) {
        return;
    }
    stack<interval> s;
    sort(arr, arr + n, compareInterval);
    s.push(arr[0]);
    for (int i = 1; i < n; ++i) {
        interval top = s.top();
        if (top.end < arr[i].start) {
            s.push(arr[i]);
        } else if(top.end < arr[i].end) {
            top.end = arr[i].end;
            s.pop();
            s.push(top);
        }
    }
    cout << "Merged intervals: " << endl;
    while (!s.empty()) {
        interval i = s.top();
        cout << "{" << i.start << ", " << i.end << "}" << " ";
        s.pop();
    }
    cout << endl;
}
int main(){
    interval arr[] = {{12, 14}, {11, 13}, {20, 22}, {21, 23}};
    mergeOverlappingIntervals(arr, SIZE(arr));
    return 0;
}

出力結果

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

Merged intervals:
{20, 23} {11, 14}

出力の順序が逆になっているのは、スタックがLIFO（後入れ先出し）構造であるためです。開始時刻の昇順に表示したい場合は、結果を一旦配列などに保存してから逆順に出力するとよいでしょう。

計算量

• 時間計算量： O(n log n) ― 区間のソートに O(n log n)、マージ処理自体は各要素を一度ずつ処理するため O(n) で完了します。
• 空間計算量： O(n) ― マージ結果を保持するためのスタックが必要になります。