Boats to Save People

Share

You are given an array people, where people[i] is a person's weight, and an unlimited number of boats that each carry at most limit weight and at most two people. Every person weighs at most limit. Return the minimum number of boats needed to carry everyone. This is LeetCode 881.

Example 1
Input: people = [1, 2], limit = 3
Output: 1
Example 2
Input: people = [3, 2, 2, 1], limit = 3
Output: 3
Explanation: boats (1, 2), (2) and (3).
Example 3
Input: people = [3, 5, 3, 4], limit = 5
Output: 4
Explanation: no two people fit together.

How to Think About It

Step 1: Look at the heaviest person

The heaviest person needs a boat no matter what. The only question is whether someone can share it. The person most likely to fit is the lightest one.

Step 2: Pair the heaviest with the lightest when possible

  • If heaviest + lightest ≤ limit, put them together.
  • Otherwise nobody fits with the heaviest person (everyone else is at least as heavy as the lightest), so they go alone.

Why pairing with the lightest is never a mistake: if a best plan pairs the heaviest person with someone else, swapping that partner with the lightest person keeps both boats within the limit.

Step 3: Two pointers on the sorted array

Sort, put light at the start and heavy at the end. Each step uses one boat, always moves heavy left, and moves light right only when they share.

Walkthrough

people = [3, 2, 2, 1], limit = 3; sorted: [1, 2, 2, 3].

LightestHeaviestSumBoat carriesBoats
134 > 3(3)1
123(1, 2)2
22 (same person)(2)3

Java Solution

The loop runs while light <= heavy, so a last person left alone still gets a boat.

Java
import java.util.Arrays;

public class BoatsToSavePeople {
    public int numRescueBoats(int[] people, int limit) {
        Arrays.sort(people);
        int light = 0;
        int heavy = people.length - 1;
        int boats = 0;
        while (light <= heavy) {
            if (people[light] + people[heavy] <= limit) {
                light++; // the lightest person shares the boat
            }
            heavy--; // the heaviest person always leaves
            boats++;
        }
        return boats;
    }
}

The original implementation, BoatsToSavePeople.java, is on GitHub.

Complexity
  • Time: O(n log n) for the sort; the two-pointer pass is O(n).
  • Space: O(1) besides the sort.

The same two pointers from both ends drive Two Sum II.