i-th person has weight
people[i], and each boat can carry a maximum weight of
Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most
Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)
Input: people = [1,2], limit = 3 Output: 1 Explanation: 1 boat (1, 2)
Input: people = [3,2,2,1], limit = 3 Output: 3 Explanation: 3 boats (1, 2), (2) and (3)
Input: people = [3,5,3,4], limit = 5 Output: 4 Explanation: 4 boats (3), (3), (4), (5)
1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000
import pytest from .Day13_BoatsToSavePeople import Solution s = Solution() @pytest.mark.parametrize( "people,limit,expected", [ ([1, 2], 3, 1), ([3, 2, 2, 1], 3, 3), ([3, 5, 3, 4], 5, 4), ([2, 2], 6, 1), ([3, 1, 7], 7, 2), ([2, 4], 5, 2), ], ) def test_num_rescue_boats(people, limit, expected): assert s.numRescueBoats(people, limit) == expected
from typing import List class Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: people.sort() boats = 0 i = 0 j = len(people) - 1 while i <= j: i = i + 1 if people[i] + people[j] <= limit else i boats += 1 j -= 1 return boats
I tried every which way to not have to sort the list for this. I tried crazy stuff like using a HashMap to store calculations but if there's a better performing solution where you don't have to sort the list first, I am not currently capable of figuring it out.
In the above solution, we first sort the people by weight, lightest to heaviest. Recall there was a requirement:
Each boat carries at most 2 people at the same time
This kind of makes our job easier since we only need to check if the heaviest person + the lightest person can fit. If
heaviest + lightest > limit then no other combination of
heaviest and anything else can work.
Given that fact, we look at the heaviest and lightest in each iteration. If they both fit, we count one boat. If not, heaviest gets their own boat because It is guaranteed each person can be carried by a boat. We keep the index at the lightest person if that's the case and check them with the next heaviest person.
log N here and we go over the list once more to count the boats giving
O(N log N).