C++で区間を挿入する方法：重なる区間のマージアルゴリズムを解説

問題概要

互いに重ならない区間（インターバル）の集合が与えられます。この集合に対して新しい区間を挿入し、必要であれば重なる区間をマージ（統合）して結果を求めます。

例えば、既存の区間が [[1,4],[6,9]] で、挿入する新しい区間が [2,5] の場合、出力は [[1,5],[6,9]] となります。新しい区間 [2,5] は既存の区間 [1,4] と重なっているため、両者が統合されて [1,5] になるからです。

アルゴリズムの流れ

この問題は、以下の手順で解くことができます。

• 新しい区間を既存の区間リストの末尾に追加する
• 区間の開始位置を基準にリスト全体をソートする（n は区間の総数）
• 結果を格納する配列 ans を作成し、最初の区間を ans に追加する
• index を 1 に初期化する
• index < n の間、以下の処理を繰り返す
  • last := ans のサイズ − 1 とする
  • ans[last][0] と ans[last][1] の最大値が、intervals[index][0] と intervals[index][1] の最小値より小さい場合（＝区間が重なっていない場合）、intervals[index] を ans にそのまま追加する
  • そうでない場合（＝区間が重なっている場合）
    • ans[last][0] を「ans[last][0] と intervals[index][0] の最小値」で更新する
    • ans[last][1] を「ans[last][1] と intervals[index][1] の最大値」で更新する
  • index を 1 増加させる
• 最後に ans を返す

このアプローチでは、隣接する区同士の重なりを順番にチェックしながら統合していくため、シンプルかつ効率的に正しい結果が得られます。

実装例

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

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
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:
    static bool cmp(vector <int> a, vector <int> b){
        return a[0]<b[0];
    }
    vector<vector <int>>insert(vector<vector <int> >& intervals, vector <int>& newInterval) {
        intervals.push_back(newInterval);
        sort(intervals.begin(),intervals.end(),cmp);
        int n = intervals.size();
        vector <vector <int>> ans;
        ans.push_back(intervals[0]);
        int index = 1;
        while(index<n){
            int last = ans.size()-1;
            if(max(ans[last][0],ans[last][1])<min(intervals[index][0],intervals[index][1])){
                ans.push_back(intervals[index]);
            } else {
                ans[last][0] = min(ans[last][0],intervals[index][0]);
                ans[last][1] = max(ans[last][1],intervals[index][1]);
            }
            index++;
        }
        return ans;
    }
};
main(){
    vector<vector<int>> v = {{1,4},{6,9}};
    vector<int> v1 = {2,5};
    Solution ob;
    print_vector(ob.insert(v, v1));
}

入力

[[1,4],[6,9]]
[2,5]

出力

[[1, 5],[6, 9]]

計算量

• 時間計算量：O(n log n) ― 区間のソート処理が支配的です。ソート後のマージ処理は O(n) で完了します。
• 空間計算量：O(n) ― マージ結果を格納するための配列 ans が必要です。