C++で学ぶKleeのアルゴリズム：線分の和集合の長さを求める方法

このチュートリアルでは、数直線上にある複数の線分について、その和集合（ユニオン）の長さを求めるプログラムをC++で作成します。

各線分の始点と終点が与えられ、それらの線分がカバーする範囲全体の合計の長さを計算するのが目的です。この問題を効率的に解く手法として知られているのが、Kleeのアルゴリズム（Klee's Algorithm）です。

それでは、問題を解くための手順を順番に見ていきましょう。

Kleeのアルゴリズムの手順

1. すべての線分の座標を配列に格納します。
2. 線分配列の2倍のサイズを持つベクター points を用意します。
3. 線分配列を走査します。
   • 現在の線分の始点と false のペアを、points のインデックス i * 2 に格納します。
   • 現在の線分の終点と true のペアを、points のインデックス i * 2 + 1 に格納します。
4. points 配列をソートします。
5. カウンター変数を使いながら points 配列を走査します。
   • カウンターが0より大きい場合は、隣接する2点 points[i] と points[i-1] の座標の差を結果に加算します。
   • 要素が終点（true）であればカウンターを減算し、始点（false）であれば加算します。
6. 最後に結果を返します。

このアルゴリズムのポイントは、「始点でカウンターを+1、終点で−1する」というシンプルな考え方にあります。カウンターが0より大きい間は、その区間を少なくとも1つの線分が覆っていることを意味します。したがって、覆われている区間の長さだけを結果に足し込むことで、線分同士の重なりを自動的に排除し、和集合の正確な長さを求められます。

実装例

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
int segmentUnionLength(const vector<pair <int,int>> &segments) {
    int n = segments.size();
    vector<pair<int, bool>> points(n * 2);
    for (int i = 0; i < n; i++) {
        points[i*2] = make_pair(segments[i].first, false);
        points[i*2 + 1] = make_pair(segments[i].second, true);
    }
    sort(points.begin(), points.end());
    int result = 0, count = 0;
    for (int i = 0; i < n * 2; i++){
        if (count) {
            result += points[i].first - points[i-1].first;
        }
        points[i].second ? count-- : count++;
    }
    return result;
}
int main() {
    vector<pair<int,int>> segments;
    segments.push_back(make_pair(1, 3));
    segments.push_back(make_pair(2, 7));
    segments.push_back(make_pair(6, 12));
    segments.push_back(make_pair(13, 5));
    cout << segmentUnionLength(segments) << endl;
    return 0;
}

出力

上記のコードを実行すると、次の結果が出力されます。

6

計算量

このアルゴリズムの計算量も確認しておきましょう。

• 時間計算量：O(n log n) ― 処理全体の中で座標ペアのソートが最もコストがかかるためです。
• 空間計算量：O(n) ― 線分数の2倍のサイズの補助配列が必要になります。

すべての区間の組み合わせを総当たりで比較する方法（O(n²)）と比べても、Kleeのアルゴリズムは非常に効率的であることがわかります。

まとめ

今回は、Kleeのアルゴリズムを使って線分の和集合の長さを求める方法を解説しました。座標をソートし、カウンターで各区間の覆われ状況を管理するという発想により、重なり合う線分を含む問題でも効率よく解けるのが大きな魅力です。本チュートリアルについて質問がある場合は、コメント欄でお気軽にお知らせください。