C++で区間リストから指定範囲を削除するアルゴリズムと実装例

問題の概要

ソート済みの互いに重ならない区間リストが与えられたとします。各区間 intervals[i] = [a, b] は、a <= x < b を満たす数値 x の集合を表します。このリスト内の各区間と、指定された区間 toBeRemoved との共通部分（重なり）をすべて取り除き、処理後の区間をソート済みリストとして返すのが目的です。

例えば、入力が [[0,2], [3,4], [5,7]]、toBeRemoved が [1, 6] の場合、出力は [[0, 1], [6, 7]] となります。

解決のための手順

補助関数 manipulate2() の定義

まず、行列 a と配列 y を受け取る補助メソッド manipulate2() を次のように定義します。

1. x を行列 a の最終行とし、その最終行を a から削除する
2. z を x のコピーとして作成する
3. x[0] := y[1]、z[1] := y[0] と設定する
4. z[0] < z[1] を満たす場合は z を a に挿入する
5. x[0] < x[1] を満たす場合は x を a に挿入する

この処理により、元の区間は「削除区間より手前の部分」と「削除区間より後ろの部分」に分割されます。条件判定を設けることで、幅を持たない空の区間は自動的に除外されます。

メイン処理 removeInterval() の流れ

1. 結果を格納する行列 ans を用意し、n を入力行列 in の行数とする
2. i が 0 から n-1 になるまで以下を繰り返す
   ・in[i] を ans に追加する
   ・a を ans の最終行、b を t（削除対象区間）とする
   ・a[0] > b[0] であれば a と b を入れ替える
   ・a と b が交差している場合、manipulate2(ans, t) を呼び出す
3. 最後に ans を返して処理完了

C++による実装例

理解を深めるために、以下の実装例を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << "[";
        for(int j = 0; j <v[i].size(); j++){
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]"<<endl;
}
class Solution {
public:
    bool isIntersect(vector <int> a, vector <int> b){
        return max(a[0], a[1]) >= min(b[0], b[1]);
    }
    void manipulate2(vector < vector <int> > &a, vector <int> y){
        vector <int> x = a.back();
        a.pop_back();
        vector <int> z = x;
        x[0] = y[1];
        z[1] = y[0];
        if(z[0] < z[1])a.push_back(z);
        if(x[0] < x[1])a.push_back(x);
    }
    vector<vector<int>> removeInterval(vector<vector<int>>& in, vector<int>& t) {
        vector < vector <int> > ans;
        int n = in.size();
        for(int i = 0; i < n; i++){
            ans.push_back(in[i]);
            vector <int> a;
            vector <int> b;
            a = ans.back();
            b = t;
            if(a[0]>b[0])swap(a, b);
            if(isIntersect(a, b)){
                manipulate2(ans, t);
            }
        }
        return ans;
    }
};
main(){
    vector<int> v2 = {1,6};
    vector<vector<int>> v1 = {{0,2},{3,4},{5,7}};
    Solution ob;
    print_vector(ob.removeInterval(v1, v2));
}

入力

[[0,2],[3,4],[5,7]]
[1,6]

出力

[[0, 1],[6, 7]]

コードのポイント

• isIntersect()：2つの区間が交差しているかどうかを判定するヘルパー関数です。
• manipulate2()：現在の区間を削除区間の前後に分割し、有効な部分だけを結果に反映します。
• 出力の末尾に余分なカンマが表示されているのは、print_vector() の実装仕様によるものです。