Boats to Save People

Minimum number of boats to save all the people, such that each boat can carry only limited weight

Boats to Save People

Problem Statement

A large ship carrying many passengers is sinking. We need to evacuate everyone using the minimum number of life-saving boats.

Each boat can carry at most two people at once — but only if their combined weight does not go over the boat's weight limit.

You are given an array, people, where people[i] is the weight of the ith person. You have an unlimited number of boats available, and each boat can carry a maximum weight of limit.

Return the minimum number of boats needed to carry everyone.

Examples

Example 1

Input: people = [1, 2], limit = 3

Output: 1

Explanation: 1 boat carries (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), and (5).

Constraints

• 1 ≤ people.length ≤ 5 × 10³
• 1 ≤ people[i] ≤ limit ≤ 3 × 10³

Solution

The idea is to sort everyone by weight, and try to pair up the heaviest person with the lightest person, whenever possible.

Steps

• We sort people in ascending order, from lightest to heaviest.
• We use two pointers: left, starting at the lightest person, and right, starting at the heaviest person.
• We repeat the following, as long as left has not passed right:
  • We check if the lightest and heaviest remaining people can share a boat together (their combined weight is within the limit).
    • If they can, we move left forward, since that lightest person now has a boat.
    • If they can't, the heaviest person must take a boat alone, since they're too heavy to pair with even the lightest remaining person.
  • Either way, we always move right backward, since the heaviest remaining person always gets placed on a boat in this step (either paired up, or alone).
  • We count this as one more boat used.
• Once left passes right, everyone has been placed on a boat. We return the total number of boats used.

Code

var numRescueBoats = function(people, limit) {
    let sortedPeople = people.sort((a, b) => a - b);

    let left = 0;
    let right = sortedPeople.length - 1;
    let boat = 0;

    while (left <= right) {
        if (sortedPeople[left] + sortedPeople[right] <= limit) {
            left++;
        }
        right--;
        boat++;
    }

    return boat;
};