プログラマー:救命ボート

(質問リンク)

質問する

無人島に閉じ込められている人を救命ボートで救い出したい.救命ボートは小さく、1回に最大2人しか乗れず、重量制限もあります.
例えば、人々の体重が[70 kg、50 kg、80 kg、50 kg]であり、救命ボートの重量制限が100 kgであれば、2人目と4人目は一緒に乗ることができるが、1人目と3人目の重量の和が150 kgであるため、救命ボートの重量制限を超えて一緒に乗ることはできない.
できるだけ救命ボートで全員を助けないようにしたい.
特定の人の体重の配列と救命ボートの重量制限をパラメータとして使用する場合は、すべての人を救うために必要な救命ボートの数の最大値を返す解関数を作成します.
せいげんじょうけん

無人島に閉じ込められた人数は1人以上50000人以下.

1人当たり体重40 kg以上240 kg以下.

救命ボートの重量制限は40 kg以上240 kg以下.

救命ボートの重量制限は常に人の体重の中で最低価格より大きいため、救命できない人はいない.

I/O例
peoplelimitreturn[70, 50, 80, 50]1003[70, 80, 50]1003

に答える

一度に2人までしか乗れないので、重い人と軽い人を合わせます.

people降順

peopleの前値と後値を合わせてlimit以下なら救命ボートに2人乗せて
以上であれば、重たい救命ボート1名のみ

効率の問題で、二重砲口は使用できません.
直接配列に触れると効率が大幅に低下するので,直接配列に触れるのではなく,indexを操作することで最初のindexと最後のindexが交差したときに終了する.
ソースコード

function solution(people, limit) {
    people.sort((a,b) => b-a);
    
    let firstI = 0, lastI = people.length-1;
    while (firstI <= lastI) {
        if (people[firstI] + people[lastI] <= limit) lastI--;
        firstI++;
    }
    return firstI;
}