【C++】2つの区間リストの共通部分を2ポインタ法で効率よく求める方法

問題の概要

閉区間からなるリストが2つ与えられます。それぞれのリスト内では、区間どうしが互いに重複せず（ペアワイズに素）、昇順にソートされているものとします。このとき、2つの区間リストの共通部分（交差）を求めるのが本記事のテーマです。

閉区間 [a, b] とは、「a ≤ x ≤ b」を満たす実数 x 全体を表す集合のことです。2つの閉区間の共通部分は、空集合になるか、あるいは再び1つの閉区間として表されることが知られています。

たとえば、次のような入力を考えてみましょう。

• A = [[0,2], [5,10], [13,23], [24,25]]
• B = [[1,5], [8,12], [15,24], [25,27]]

この場合の出力は [[1,2], [5,5], [8,10], [15,23], [24,24], [25,25]] となります。

アプローチ：2ポインタ法

両リストともソート済みであるため、2ポインタ法を使うと効率的に解けます。A の i 番目の区間と B の j 番目の区間を先頭から同時に走査し、交差していれば結果に追加し、終点が早い方のポインタを進めていくのが基本戦略です。

アルゴリズムの手順

1. 結果を格納する配列 res を用意し、ポインタ i と j を 0 で初期化します。
2. i < A.size() かつ j < B.size() の間、以下を繰り返します。
3. 共通部分の候補として、始点 lo を max(A[i][0], B[j][0])、終点 hi を min(A[i][1], B[j][1]) とします。
4. lo ≤ hi であれば、区間 [lo, hi] は実際に交差しているので res に追加します。
5. A[i][1] < B[j][1]（A 側の区間が先に終わる）なら i を、そうでなければ j を1進めます。

C++での実装例

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<int>> intervalIntersection(vector<vector<int>>& A,
                                             vector<vector<int>>& B) {
        vector<vector<int>> result;
        int i = 0, j = 0;
        while (i < (int)A.size() && j < (int)B.size()) {
            // 共通部分の候補：始点は大きい方、終点は小さい方
            int lo = max(A[i][0], B[j][0]);
            int hi = min(A[i][1], B[j][1]);
            if (lo <= hi) {              // 実際に交差している場合のみ追加
                result.push_back({lo, hi});
            }
            // 終点が早い側のポインタを進める
            if (A[i][1] < B[j][1]) i++;
            else                   j++;
        }
        return result;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> A = {{0,2},{5,10},{13,23},{24,25}};
    vector<vector<int>> B = {{1,5},{8,12},{15,24},{25,27}};

    vector<vector<int>> ans = ob.intervalIntersection(A, B);

    cout << "[";
    for (size_t k = 0; k < ans.size(); ++k) {
        cout << "[" << ans[k][0] << ", " << ans[k][1] << "]";
        if (k + 1 < ans.size()) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}

入力

A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,27]]

出力

[[1, 2], [5, 5], [8, 10], [15, 23], [24, 24], [25, 25]]

動作のポイント

• 交差判定：2つの閉区間 [a1, b1] と [a2, b2] が交差するのは、max(a1, a2) ≤ min(b1, b2) が成り立つときです。
• ポインタの進め方：終点が早い側の区間は、相手側の残りのどの区間ともこれ以上交差しないため、そのポインタを安全に進められます。
• 単一点の区間：[5,5] のように始点と終点が一致する区間も、有効な結果として正しく扱われます。

計算量

• 時間計算量：O(n + m)（n、m はそれぞれ A、B の区間数）。各ステップで必ずどちらかのポインタが1つ進むためです。
• 空間計算量：出力を除き O(1)。入力リストを書き換えることなく処理できます。

まとめ

ソート済みの区間リスト同士の共通部分は、2ポインタ法によって線形時間で求められます。「始点の最大値」と「終点の最小値」を比較して交差を判定し、終点が早い側のポインタを進めるというシンプルなルールだけで実装できるのが魅力です。マージソートのマージ処理に似た発想なので、覚えておくとカレンダーの予定重複チェックなど、さまざまな場面で応用できるテクニックです。