Boats to Save People

Carry everyone across in the fewest boats, two people per boat, by pairing the heaviest person with the lightest.

You are given an array people, where people[i] is the weight of one person, and a number limit. There are as many boats as needed. Each boat carries at most two people, and their weights together may be at most limit. No person weighs more than limit. Return the smallest number of boats that carries everyone.

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

The Idea

Picture a group of people on a river bank and a row of small boats. A boat takes one or two people, as long as their weights together stay within the limit. Everyone has to cross, and we want to use as few boats as we can.

Take Example 2: the weights are 3, 2, 2 and 1, and the limit is 3. The person who weighs 3 fills a boat alone, because anyone added would go over 3. The two people who weigh 2 cannot share either, since 2 + 2 = 4. The person who weighs 1 can join either of them. So three boats is the best: 3 alone, 1 with a 2, and the other 2 alone.

With four people we can check every way of pairing them up by hand. With thousands of people that is hopeless, because the number of ways grows far faster than the number of people. So who should share a boat with whom?

Start with the heaviest person, who needs a boat in any plan. Who can join them? If anyone can, the lightest person can, because everyone else weighs at least as much. And if even the lightest person does not fit, nobody does, so the heaviest person goes alone.

When the lightest person does fit, is putting the two together ever a mistake? No. Suppose a plan puts the heaviest person with someone else, X, and the lightest person in another boat. Swap X and the lightest person. The heaviest person's boat only gets lighter. X now sits where the lightest person was, next to someone who weighs no more than the heaviest person, and X already fit next to the heaviest person. So both boats stay within the limit, and the number of boats does not change.

That gives a simple rule: fill each boat with the heaviest person left, plus the lightest person left if they fit. Making the choice that looks best right now, and never going back on it, is called a greedy approach.

To find the lightest and the heaviest person quickly, sort the weights. Then the lightest person is always at the left end and the heaviest at the right end. Put a marker called light on the left end and another called heavy on the right end. Look at the picture below, for Example 2.

The sorted weights 1, 2, 2, 3 with limit 3. First light is on 1 and heavy on 3: 1 + 3 = 4 is over the limit, so boat 1 carries 3 alone. Then light is on 1 and heavy on 2: 1 + 2 = 3 fits, so boat 2 carries 1 and 2. Last, light and heavy meet on the other 2, and boat 3 carries 2 alone.

In the first row, light is on 1 and heavy on 3. Their sum, 4, is over the limit, so boat 1 carries 3 alone and heavy moves left. In the second row, 1 + 2 = 3 fits, so boat 2 carries both people, and both markers move inward. In the last row, the markers meet on the other 2, the only person left, and boat 3 carries that person alone.

Every boat takes away the heaviest person left, and sometimes the lightest too, so the two markers close in from both ends. Two markers that start at opposite ends of a sorted array and walk toward each other are called the two-pointer technique.

Solution Approach

Turning that idea into code means settling three things: how to find the lightest and heaviest person left, when each marker moves, and when the loop stops.

Finding the lightest and heaviest person

Do we need to sort? Without sorting, each boat would need a scan over everyone still waiting to find the heaviest and the lightest. For n people that is about n × n steps. Sorting once is much cheaper, and after it the lightest and heaviest person left always sit under the two markers.

Moving the markers

Which marker moves after each boat? heavy always moves left, because the heaviest person leaves in that boat whether or not someone joins. light moves right only when the lightest person fit and joined. The fit test is people[light] + people[heavy] <= limit, with <= because a boat may carry exactly the limit.

Stopping the loop

When is everyone across? The loop runs while light <= heavy. When the markers sit on the same position, one person is still waiting, like the last 2 in the picture, and still needs a boat. In that pass the fit test adds that person's weight twice, and it may pass or fail. Either way heavy moves past light, and exactly one boat is counted.

Java Solution

The method numRescueBoats works in these steps:

  1. First, sort the weights with Arrays.sort(people), so the lightest person is at the start and the heaviest at the end.
  2. Put the marker light at position 0 and heavy at the last position, people.length - 1. Start the counter boats at 0.
  3. Loop while light <= heavy. In each pass, check whether people[light] + people[heavy] is at most limit. If it is, the lightest person joins the boat and light moves right.
  4. In every pass, move heavy left, because the heaviest person has left, and add one to boats.
  5. When the markers have crossed, everyone has a boat, so return boats.

The main method runs the three examples, two people whose weights add up to exactly the limit, a single person, and four people who pair up neatly. Its last line prints the Example 2 array after the call.

Java
import java.util.Arrays;

public class BoatsToSavePeople {

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

    public static void main(String[] args) {
        System.out.println(numRescueBoats(new int[] {1, 2}, 3));
        int[] people = {3, 2, 2, 1};
        System.out.println(numRescueBoats(people, 3));
        System.out.println(numRescueBoats(new int[] {3, 5, 3, 4}, 5));
        System.out.println(numRescueBoats(new int[] {2, 2}, 4));
        System.out.println(numRescueBoats(new int[] {3}, 3));
        System.out.println(numRescueBoats(new int[] {5, 1, 4, 2}, 6));
        System.out.println(Arrays.toString(people));
    }
}

Running it prints:

Output
1
3
4
1
1
2
[1, 2, 2, 3]

The second line, 3, is Example 2 and the three boats from the picture. The third line, 4, is Example 3, where no two people fit together, so each person gets a boat. The fourth line, 1, comes from [2, 2] with limit 4: 2 + 2 is exactly the limit, and <= lets the two share a boat. The fifth line, also 1, is the single person [3]: the markers start on the same position, and the loop still runs once.

The sixth line comes from [5, 1, 4, 2] with limit 6, sorted to 1, 2, 4, 5. The person of 1 rides with 5 and the person of 2 with 4, so two boats are enough.

Look at the last line: [1, 2, 2, 3] is the Example 2 array after the call. Arrays.sort sorted the caller's own array, so pass a copy if the original order matters.

Why light <= heavy and not light < heavy? With <, the loop stops as soon as the markers meet and never gives the last person a boat. Running that version returns 2 for Example 2 instead of 3, and 0 for [3] instead of 1.

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

Complexity

The work is the sort, plus one walk of the two markers toward each other.

  • Time: O(n log n), where n is the number of people. Sorting takes O(n log n). The loop then runs at most n times, because every pass moves heavy one step left, and each pass does a fixed amount of work.
  • Space: O(1) besides the sort. The loop keeps three int variables, light, heavy and boats, and Arrays.sort reorders the array itself instead of making a sorted copy.

The same two markers, walking in from both ends of a sorted array, find a pair with a given sum in Two Sum II.