問題の説明

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

せいげんじょうけん

無人島に閉じ込められている人は1人以上50000人以下です.
一人当たりの体重は40キロ以上240キロ以下です.
救命ボートの重量は40キロまたは240キロ以下に制限されている.
救命ボートの重量制限はいつも人々の体重の中で最低価格より大きいので、助けられない人はいません.

I/O例

people			limit		return
[70, 50, 80, 50]	100		3
[70, 80, 50]		100		3

方法

人の体重を昇順に並べた後、一番前と一番後ろの人の体重の和がlimit以下であれば、並べ替えから一番前と一番後ろの人を除去する方法で近づく.一番前の人を除いたときにpop(0)を使うとO(n)の時間的複雑度が発生し、結果的にO(n^2)の時間的複雑度が必要になるのがタイムアウトの原因です.O(n)上で時間の複雑さを解決するためにはdequeのpopleft()を用いて先頭の人を削除する必要がある.

ボートの数を格納する変数の答えを0と定義します.

昇順で

人.

人をデックの形態に変換してdqに格納した.

dqの間、ドアを繰り返し回転させる.
->dqの長さが1の場合、答えを1に増やし、dpをポップアップします.△まだ一人残っていれば、必ず乗船できるので、一人で乗船します.
->その他の場合、
-->dq[0]+dq[-1]が限界以下の場合、dq左pop、pop、responseは1増加します.
-->dq[0]+dq[-1]が限界より大きい場合、dpをポップアップし、1つの答えを追加します.(昇順ソートであるため、dp[0]+dq[1]がlimitより大きい場合、もちろんdq[1]+dq[1]もlimitより大きいため、最も重い人だけが乗船できる.)

の答えを返します.

solution.py

from collections import deque
def solution(people, limit):
    answer = 0
    people.sort()
    dq=deque(people)
    while dq:
        if len(dq)==1:
            answer+=1
            dq.pop()
        else:
            if dq[0]+dq[-1]<=limit:
                dq.popleft()
                dq.pop()
                answer+=1
            elif dq[0]+dq[-1]>limit:
                dq.pop()
                answer+=1
    return answer