C++で他の区間に包含される区間を削除するアルゴリズム

問題の概要

区間のリストが与えられ、リスト内の他の区間に包含されている（カバーされている）すべての区間を取り除いたうえで、最後に残った区間の個数を返すことを考えます。

ここで、区間 [a, b) が区間 [c, d) に包含されるとは、c <= a かつ b <= d が成り立つ場合を指します。

たとえば、入力が [[1,4],[3,6],[2,8]] の場合、出力は 2 になります。このとき区間 [3,6] は [2,8] に完全に含まれているため削除され、残るのは [1,4] と [2,8] の 2 つの区間です。

解法のアプローチ

この問題は、区間を終了時刻でソートしたうえでスタックを活用することで、効率的に解くことができます。具体的な手順は以下の通りです。

• 区間のリストを終了時刻の昇順でソートします
• 空のスタック st を用意します
• i を 0 から a のサイズ − 1 まで順に処理します
  • スタックが空であるか、a[i] とスタックトップの区間が互いに包含関係にない場合は、a[i] を st にプッシュします
  • それ以外の場合は、次のように処理します
    • temp := a[i] とします
    • st が空でなく、temp とスタックトップの区間が包含関係にある限り、スタックから要素をポップします
    • temp を st にプッシュします
• 最後に st のサイズを返します

C++による実装例

それでは、実際のC++のコードを見ていきましょう。

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool intersect(vector <int>& a, vector <int>& b){
        return (b[0] <= a[0] && b[1] >= a[1]) || (a[0] <= b[0] && a[1] >= b[1]);
    }
    static bool cmp(vector <int> a, vector <int> b){
        return a[1] < b[1];
    }
    void printVector(vector < vector <int> > a){
        for(int i = 0; i < a.size(); i++){
            cout << a[i][0] << " " << a[i][1] << endl;
        }
        cout << endl;
    }
    int removeCoveredIntervals(vector<vector<int>>& a) {
        sort(a.begin(), a.end(), cmp);
        stack < vector <int> > st;
        for(int i = 0; i < a.size(); i++){
            if(st.empty() || !intersect(a[i], st.top())){
                st.push(a[i]);
            }
            else{
                vector <int> temp = a[i];
                while(!st.empty() && intersect(temp, st.top())){
                    st.pop();
                }
                st.push(temp);
            }
        }
        return st.size();
    }
};
main(){
    vector<vector<int>> v = {{1,4},{3,6},{2,8}};
    Solution ob;
    cout << (ob.removeCoveredIntervals(v));
}

コードのポイント

• intersect 関数： 2つの区間のうち、どちらか一方がもう一方を完全に含んでいるかどうかを判定します
• cmp 関数： 終了時刻（a[1]）を基準に区間を昇順ソートするための比較関数です
• removeCoveredIntervals 関数： ソート後、スタックを使って包含関係にある区間を順次除去し、最終的に残った区間数を返します

計算量は、ソートに O(n log n)、各区間の処理全体でも各要素は高々1回のプッシュとポップしか行われないため、全体で O(n log n) となります。

入力

[[1,4],[3,6],[2,8]]

出力

2