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 peoplepeople[i]limitlimitlimit
Example 1
Output: 1
Example 2
Output: 3
Explanation: boats (1, 2), (2) and (3).
Example 3
Output: 4
Explanation: no two people fit together.
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 lightheavy
In the first row, lightheavyheavy
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? heavylightpeople[light] + people[heavy] <= limit<=
Stopping the loop
When is everyone across? The loop runs while light <= heavyheavylight
Java Solution
The method numRescueBoats
- First, sort the weights with
, so the lightest person is at the start and the heaviest at the end.Arrays.sort(people) - Put the marker
at position 0 andlight at the last position,heavy . Start the counterpeople.length - 1 at 0.boats - Loop while
. In each pass, check whetherlight <= heavy is at mostpeople[light] + people[heavy] . If it is, the lightest person joins the boat andlimit moves right.light - In every pass, move
left, because the heaviest person has left, and add one toheavy .boats - When the markers have crossed, everyone has a boat, so return
.boats
The main
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:
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]<=[3]
The sixth line comes from [5, 1, 4, 2]
Look at the last line: [1, 2, 2, 3]Arrays.sort
Why light <= heavylight < heavy<[3]
The original implementation,
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
one step left, and each pass does a fixed amount of work.heavy - Space: O(1) besides the sort. The loop keeps three
variables,int ,light andheavy , andboats reorders the array itself instead of making a sorted copy.Arrays.sort
The same two markers, walking in from both ends of a sorted array, find a pair with a given sum in