C++で風船をすべて割るために必要な矢の最小本数を求める方法

問題概要

二次元空間上に複数の球形の風船が浮かんでいるとします。各風船については、その水平方向の直径の始点座標と終点座標が与えられ、始点は必ず終点より小さくなっています。風船の数は最大 10⁴ 個です。

矢は x 軸上の任意の位置から真上へ垂直に射出できます。位置 xstart から xend にある風船は、xstart ≤ x ≤ xend を満たす位置 x から射出された矢によって破裂します。射出できる矢の本数に制限はなく、一度射出された矢は無限に上方へ飛び続けるものとします。

このとき、すべての風船を破裂させるために必要な矢の最小本数を求めるのがこの問題です。

具体例

入力が [[10,16],[2,8],[1,6],[7,12]] の場合、出力は 2 になります。

• x = 6 から矢を射出すると、[2,8] と [1,6] の風船が破裂する
• もう1本を x = 11 から射出すると、[10,16] と [7,12] の風船が破裂する

つまり、わずか2本の矢ですべての風船を割ることができます。

解法アプローチ（貪欲法）

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

• 風船の位置情報を格納した配列 pos を用意する
• pos 配列を終点座標を基準にソートする
• n := 風船の総数。n が 0 の場合は 0 を返す
• currEnd := ソート後の最初の風船の終点座標
• cnt := 1（最初の矢は必ず必要）
• i を 1 から n−1 までループ：
  • currEnd ＜ pos[i] の始点座標ならば、cnt を1増やし、currEnd := pos[i] の終点座標に更新する
• 最後に cnt を返す

このアルゴリズムのポイントは、終点座標でソートしておくことで、「現在の矢が届く範囲（currEnd）より先に始まる風船には新しい矢が必要だ」と即座に判断できることです。こうして1本の矢でできるだけ多くの風船を割るように選んでいくと、結果的に必要な矢の最小本数が求まります。

C++実装例

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    bool intersect(vector<int>& a, vector<int>& b){
        return a[1] >= b[0];
    }
    static bool cmp(vector<int>& a, vector<int>& b){
        return a[1] < b[1];
    }
    void manipulate(vector<int>& a, vector<int>& b){
        a[0] = min(a[0], b[0]);
        a[1] = max(a[1], b[1]);
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), cmp);
        int n = points.size();
        if(!n) return 0;
        int currEnd = points[0][1];
        int cnt = 1;
        for(int i = 1; i < n; i++){
            if(currEnd < points[i][0]){
                cnt++;
                currEnd = points[i][1];
            }
        }
        return cnt;
    }
};
main(){
    vector<vector<int>> v = {{10,16},{2,8},{1,6},{7,12}};
    Solution ob;
    cout << (ob.findMinArrowShots(v));
}

入力

[[10,16],[2,8],[1,6],[7,12]]

出力

2

計算量の評価

• 時間計算量： O(n log n) ― 風船をソートする処理が支配的です
• 空間計算量： O(1) ― ソート以外に追加のデータ構造は不要です

区間スケジューリング問題と同じ発想で解ける典型例なので、貪欲法の練習としてもおすすめの問題です。