C++で重複しない区間を作るための最小削除数を求めるアルゴリズム

問題概要

複数の区間（インターバル）のコレクションが与えられたとき、残りの区間同士が互いに重なり合わないようにするために、削除が必要な区間の最小数を求める問題です。

例えば、区間が [[1,2], [2,3], [3,4], [1,3]] であった場合、他のすべての区間が重複しない状態にするには [1,3] を削除すればよいため、出力は 1 となります。

解決のためのアプローチ

この問題は貪欲法（グリーディ法）を使うことで効率的に解くことができます。手順は以下の通りです。

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

このアプローチでは、終了時刻の早い区間から優先的に選ぶことで、後続の区間との重複を最小限に抑えることができます。

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 = {{1,2},{1,2},{1,2}};
    Solution ob;
    cout << (ob.eraseOverlapIntervals(v));
}

入力

[[1,2],[1,2],[1,2]]

出力

2

コードの解説

この実装では、まず比較関数 cmp を使って各区間を終了時刻の昇順にソートしています。その後、最初の区間の終了時刻を基準として、以降の区間の開始時刻がこの基準以上であれば重複していないと判断し、カウントを増やしていきます。

最終的な答えは「全体の区間数 n」から「重複なく選べた区間数 cnt」を引いた値、つまり削除が必要な区間の数になります。

上記の入力例では、同じ区間 [1,2] が3つ存在するため、1つだけを残して残りの2つを削除する必要があり、出力は 2 となります。

計算量について見てみると、ソートに O(n log n)、その後の走査に O(n) かかるため、全体の時間計算量は O(n log n) となります。