C++で重複する区間を取り除くために必要な最小削除数を求めるプログラム

複数の区間(インターバル)が与えられたとき、残りの区間同士が互いに重ならないようにするために削除すべき区間の最小数を求める問題について解説します。例えば、区間が [[8,10],[3,5],[6,9]] の場合、出力は 1 になります。これは [6,9] を1つ削除すれば、残りのすべての区間が重ならなくなるためです。

解決のためのアプローチ

この問題は貪欲法(グリーディーアルゴリズム)を使うことで効率的に解けます。各区間を終了時刻の昇順に並べ替え、終了時刻が早い区間から順に選んでいくことで、できるだけ多くの非重複区間を確保でき、結果として削除が必要な区間の数が最小になります。

具体的な手順は以下の通りです。

• n を配列のサイズとします
• n が 0 の場合は 0 を返します
• count を 1 で初期化します
• 配列を区間の終了時刻に基づいてソートします
• end を最初の区間の終了時刻とします
• i を 1 から n−1 まで繰り返します
  • arr[i] の開始時刻が end 以上であれば、end を arr[i] の終了時刻に更新し、count を 1 増やします
• n − count を返します

それでは、実際のC++での実装を見てみましょう。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    static bool cmp(vector <int>& a, vector <int>& b){
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& arr) {
        int n = arr.size();
        if(!n)return 0;
        int cnt = 1;
        sort(arr.begin(), arr.end(), cmp);
        int end = arr[0][1];
        for(int i = 1; i < n; i++){
            if(arr[i][0] >= end){
                end = arr[i][1];
                cnt++;
            }
        }
        return n - cnt;
    }
};
main(){
    vector<vector<int>>
    v = {{8,10},{3,5},{6,9}};
    Solution ob;
    cout << (ob.eraseOverlapIntervals(v));
}

入力

{{8,10},{3,5},{6,9}}

出力

1

アルゴリズムのポイント

このアルゴリズムでは、終了時刻が早い区間から優先的に選ぶことで、後続の区間との重なりを最小限に抑えられます。最終的に選択された区間の数(count)を全体の区間数 n から差し引くことで、削除すべき区間の最小数が求まります。計算量はソート部分が O(n log n)、走査部分が O(n) となり、非常に効率的な手法です。