[Programmers] Scialuppa di salvataggio

https://programmers.co.kr/learn/courses/30/lessons/42885

Soluzione

Leggere bene i vincoli. Ho perso molto tempo non avendo notato la condizione per cui solo 2 persone possono salire su una barca alla volta.

Quando ogni barca può portare al massimo 2 persone, la strategia più efficiente è abbinare la persona più pesante con quella più leggera. Si ordina l’array people, poi si riducono gli indici da entrambe le estremità. A patto di gestire correttamente il caso in cui una persona pesante viaggia da sola, sia l’ordinamento crescente che decrescente funzionano.

Codice

https://github.com/naem1023/codingTest/blob/master/greedy/pg-30-42885.py

1
def solution(people, limit):
2
    cnt  = 0
3
    people.sort()
4

5
    start, end = 0, len(people) - 1
6

7
    while start <= end:
8
        cnt += 1
9
        if people[start] + people[end] <= limit:
10
            start += 1
11
        end -= 1
12

13
    return cnt