Boats To Save People

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

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.

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;
};