You are given an array people where people[i] is the weight of the ithperson, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.
Return the minimum number of boats to carry every given person.
Example 1:
Input: people = [1,2], limit = 3 Output: 1 Explanation: 1 boat (1, 2)
Example 2:
Input: people = [3,2,2,1], limit = 3 Output: 3 Explanation: 3 boats (1, 2), (2) and (3)
Example 3:
Input: people = [3,5,3,4], limit = 5 Output: 4 Explanation: 4 boats (3), (3), (4), (5)
Constraints:
1 <= people.length <= 5 * 1041 <= people[i] <= limit <= 3 * 104
The description was taken from https://leetcode.com/problems/boats-to-save-people/.
#O(N) Time, O(1) Spaceclass Solution: def numRescueBoats(self, people: List[int], limit: int) -> int: boats = 0 people.sort() left, right = 0, len(people)-1 while left <= right: if people[left] + people[right] <= limit: left += 1 right -= 1 else: right -= 1 boats += 1 return boatsThe problem requires us to return the minimum number of boats that will allow us to carry all of the people.
When we see a requirement like this, most often it can be accomplished by using a greedy algorithm.
Greedy algorithms typically entail sorting the input and focusing on the most costly tasks first before considering any others so that we can conserve the most resources. In this case, the most costly tasks are the heaviest people, since there is a higher chance that they will require their own boats, more than the lightest people. The resources we are trying to save are the boats.
What we can do is sort the input and use two pointers, one pointer to signify the current heaviest person on the right, and one to signify the current lightest person on the left.
We will first see if we can pair these two people together into one boat because we don't want to give the heaviest person their own boat if somebody else can fit, we need to conserve resources. If that is not possible, then we will give the boat to the heaviest person.
Once our pointers have overlapped, we have placed each person into a boat so we will return the minimum number of boats it took to place everybody.
Let's start by creating a boat counter and sorting the input.
Once we do that, the lightest person will be on the left side of the array, and the heaviest will be on the right, so we will set two pointers for these two people.
boats = 0 people.sort() left, right = 0, len(people)-1
Now we can begin placing people into boats.
While the pointers haven't overlapped, that means we still have people to place so the loop will continue.
while left <= right:
A boat can hold at most two people.
The two people we should attempt to place are the current heaviest person and the lightest person. We don't want to give the heaviest person a boat to themself if another person can fit. And if another person can fit, our best bet would be the lightest person because if they can't fit then no other heavier person could.
If both of these people are lower than the given limit, we will place them into the boat and exclude them from our search by moving the pointers.
if people[left] + people[right] <= limit: left += 1 right -= 1
If they exceed the limit, we will just put the heaviest person and exclude this person from our search.
else: right -= 1
Whether we placed one or two people, we still needed one boat in this iteration so we will increment the count.
boats += 1
Once our pointers have overlapped, we have placed everybody into boats so let's return the number of boats it took to place everybody.
return boats