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

Link to code

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

Link to code

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

Analysis

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).