Greedy - Boats to Save People
All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.
Difficulty : Easy
Greedy, Two Pointers
Problem
You are given an array people where people[i] is the weight of the ith person, 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:
1
2
3
Input: people = [1,2], limit = 3
Output: 1
Explanation: 1 boat (1, 2)
Example 2:
1
2
3
Input: people = [3,2,2,1], limit = 3
Output: 3
Explanation: 3 boats (1, 2), (2) and (3)
Example 3:
1
2
3
Input: people = [3,5,3,4], limit = 5
Output: 4
Explanation: 4 boats (3), (3), (4), (5)
Solution
Sort the array
1
people.sort()
Pick the most heavy person. Decrease the right pointer.
1 2
remain = limit - people[right] right-=1
Then try to fit a slim person. If works then increase the left pointer.
1 2
if left <= right and remain>=people[left]: left+=1
Repeat until left is greater than right pointer.
1
while left <= right:
Final Code
Here is the full code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def num_rescue_boats(people,limit):
left = 0
right = len(people)-1
people.sort()
boats=0
while left <= right:
remain = limit - people[right]
right-=1
boats+=1
if left <= right and remain>=people[left]:
left+=1
return boats