## DEV Community is a community of 870,143 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Ruairí O'Brien

Posted on • Updated on

# Day 13 - Boats to Save People

The `i`-th person has weight `people[i]`, and each boat can carry a maximum weight of `limit`.

Each boat carries at most 2 people at the same time, provided the sum of the weight of those people is at most `limit`.

Return the minimum number of boats to carry every given person. (It is guaranteed each person can be carried by a boat.)

Example 1:

``````Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
``````

Example 2:

``````Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
``````

Example 3:

``````Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
``````

Note:

• `1 <= people.length <= 50000`
• `1 <= people[i] <= limit <= 30000`

## My Tests

``````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
``````

## My Solution

``````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
``````

## My Commentary

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.

`people.sort()` is `log N` here and we go over the list once more to count the boats giving `O(N log N)`.