C++で削除時間が待機時間以上の場合の配列からの最大削除数を求める方法

問題の概要

この問題では、N個の要素からなる配列が与えられます。各要素には「削除時間」と「待機時間」が関係しており、削除時間が待機時間以上である場合にのみ要素を削除できるという条件のもとで、配列から削除できる要素の最大数を求めるのが課題です。

配列の各要素の値は、その要素を配列から取り除くのにかかる時間(=削除時間)を表します。

また、各要素には待機時間があります。これは、その要素が実際に削除されるまでに待たなければならない時間のことです。

なお、配列内の要素の順序は、必要に応じて自由に入れ替えて構いません。

入出力例

具体例を使って問題を確認しましょう。

入力: array = {12, 3, 11, 7, 5}

出力: 2

説明:

まず、配列を昇順に並べ替えると {3, 5, 7, 11, 12} になります。

続いて、先頭から要素を1つずつ削除できるか判定していきます。

• 3 を削除: 待機時間は 0 で、削除時間(3)より小さいため削除可能。
• 5 を削除: 待機時間は 3(前の要素の削除時間の合計)で、削除時間(5)より小さいため削除可能。
• 7 を削除: 待機時間は 8(3+5)で、削除時間(7)より大きいため削除不可能。

したがって、この配列から削除できる要素の最大数は 2 となります。

解法のアプローチ

この問題は貪欲法(Greedy法)で解くことができます。削除時間の小さい要素から順に処理すれば、待機時間の増加を最小限に抑えながら、より多くの要素を削除できます。そこで、配列を昇順にソートし、先頭から順に「削除可能かどうか」を1つずつチェックしていきます。

アルゴリズム

Step 1: 配列を昇順にソートする。
Step 2: 配列の各要素について以下を繰り返す。
Step 3: 待機時間を求める(その要素より前にある全要素の削除時間の合計)。
Step 4: もし 待機時間 <= 削除時間 ならば:
    Step 4.1: その要素を削除対象とし、削除カウントを +1 する。
Step 5: そうでなければ: ループを抜ける。
Step 6: 削除した要素数を出力する。

C++での実装例

以下は、「削除時間が待機時間以上の場合の配列からの最大削除数」を求めるC++プログラムです。

#include <bits/stdc++.h>
using namespace std;

int countRemovedElements(int arr[], int n){
    sort(arr, arr + n);          // 配列を昇順にソート
    int removeCount = 0;         // 削除できた要素数
    int waitTime = 0;            // 現在の待機時間
    for (int i = 0; i < n; i++) {
        if (arr[i] >= waitTime) {
            removeCount++;       // 削除可能なのでカウントアップ
            waitTime += arr[i];  // 削除時間を待機時間に加算
        }
        else
            break;               // 削除不可能なら終了
    }
    return removeCount;
}

int main(){
    int arr[] = { 12, 3, 11, 7 , 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<"The maximum number of elements that can be removed from the array is "<<countRemovedElements(arr, n);
    return 0;
}

実行結果

The maximum number of elements that can be removed from the array is 2

計算量の評価

このアルゴリズムの計算量は以下のとおりです。

• 時間計算量: O(n log n) — 昇順ソートが支配的であり、その後の線形走査は O(n)。
• 空間計算量: O(1) — 追加の補助配列を使用しないため。

まとめ

削除時間が待機時間以上である場合の配列からの最大削除数を求める問題は、配列を昇順にソートして先頭から貪欲に判定していくだけで効率的に解けます。小さい値から順に削除することで待機時間の増加を抑えられる点が、この貪欲戦略が正しく機能する鍵となります。