Problem
You are given an integer arraypeople, where people[i] represents the weight of a person, and an integer limit representing the maximum weight a boat can carry.
Each boat can carry at most two people. Return the minimum number of boats required to carry everyone.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
people = [3,2,2,1]
limit = 3Output
3Solution
This problem can be solved using a Greedy Approach.We first sort the people by their weight. We then use two pointers:
smallest points to the lightest person and largest points to the heaviest person.
The heaviest person should always be assigned to a boat. If the lightest and heaviest people can fit together within the limit, we move
smallest forward. Otherwise, the heaviest person travels alone.
After assigning the heaviest person, we always move
largest backward and increase the boat count.
When both pointers point to the same person, that person needs one final boat.
class Solution {
public int numRescueBoats(int[] people, int limit) {
Arrays.sort(people);
int boats = 0;
int smallest = 0;
int largest = people.length - 1;
while (smallest <= largest) {
boats++;
// Pair smallest and largest if possible
if (people[smallest] + people[largest] <= limit)
smallest++;
// Largest person gets a boat
largest--;
}
return boats;
}
}
Complexity
Sorting the array takesO(n log n) time, and the two-pointer traversal takes O(n) time, resulting in O(n log n) overall time complexity.
The two-pointer approach uses
O(1) extra space apart from the space used internally by sorting.