C++ですべてのバナーを吊るすのに必要な最小ピン数を求めるプログラム

区間 [start, end] のリストが与えられ、これは掛けたいバナーの開始位置と終了位置を表しているとします。バナーを掛けるには最低でも1本のピンが必要で、1本のピンで複数のバナーを同時に掛けることも可能です。ここでは、すべてのバナーを掛けるために必要な最小限のピン数を求めます。

問題の例

たとえば、入力が intervals = [[2, 5], [5, 6], [8, 10], [10, 13]] の場合、出力は 2 になります。位置 5 と 10 の2か所にピンを打つことで、すべてのバナーを掛けられるためです。

解法の考え方

この問題は貪欲法を使うことで効率的に解けます。各区間を「終了位置の昇順」にソートし、まだピンで覆われていない区間が見つかるたびに、その終了位置にピンを配置します。終了位置を選ぶことで、後続の区間が同じピンでカバーされる可能性が最大化されます。

手順

• 区間のリスト v を終了値を基準にソートする
• ret := 0（必要なピン数のカウンタ）
• last := -inf（最後に置いたピンの位置）
• v の各要素 it に対して以下を繰り返す：
  • last >= it の開始位置 ならば、このバナーはすでにカバーされているのでスキップして次へ
  • そうでなければ ret を1増やし、last := it の終了位置 とする
• 最後に ret を返す

C++の実装例

以下の実装を見ると理解が深まります。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        return a.back() < b.back();
    }
    int solve(vector<vector<int>>& v) {
        sort(v.begin(), v.end(), cmp);
        int ret = 0;
        int last = -1e8;
        for (auto& it : v) {
            if (last >= it[0]) {
                continue;
            }
            ret++;
            last = it[1];
        }
        return ret;
    }
};
int solve(vector<vector<int>>& intervals) {
    return (new Solution())->solve(intervals);
}
int main(){
    vector<vector<int>> v = {{2, 5},{5, 6},{8, 10},{10, 13}};
    cout << solve(v);
}

入力

{{2, 5},{5, 6},{8, 10},{10, 13}}

出力

2

計算量

区間のソートに O(n log n)、その後の走査に O(n) かかるため、全体の時間計算量は O(n log n) です。追加の記憶領域は定数個の変数のみで済み、空間計算量は O(1) となります。