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
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
What is the worst case running time for finding an element in a binary search tree(not necessarily balanced) of size n?
Solution Implementation
In a binary min heap, the maximum element can be found in:
Which data structure is used to implement priority queue?
Recommended Readings
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
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 Teaching 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.