Boats to Save People
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:
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 * 104
1 <= people[i] <= limit <= 3 * 104
Solution
We wish to perform two pointers in opposite directions on a sorted array people
.
To optimize the number of boats, we can assign a light weight person with a heavy person.
Just as Two Sum Sorted try to pair two numbers adding up to sum
, we try to pair two people with weight less than or equal to limit
.
If their total weight is more than the limit, then we can only assign the person with the heavier weight (person[r]
) onto the boat so that the lighter person may be paired with someone else.
Implementation
1def numRescueBoats(self, people: List[int], limit: int) -> int:
2 people.sort()
3 l, r = 0 , len(people)-1
4 boat = 0
5 while l <= r:
6 if people[l] + people[r] <= limit:
7 l += 1
8 boat += 1
9 r -= 1
10 return boat
Which data structure is used to implement priority queue?
Solution Implementation
Which of these properties could exist for a graph but not a tree?
Recommended Readings
Patterns The Shortest Path Algorithm for Coding Interviews The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we can determine the
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.