Boats to Save People

Try to solve the Boats to Save People challenge.

We'll cover the following

Statement#

A big ship with numerous passengers is sinking, and there is a need to evacuate these people with the minimum number of life-saving boats. Each boat can carry, at most, two persons however, the weight of the people cannot exceed the carrying weight limit of the boat.

We are given an array, people, where people[i] is the weight of the ithi^{th} person, and an infinite number of boats, where each boat can carry a maximum weight, limit. Each boat carries, at most, two people at the same time. This is provided that the sum of the weight of these people is under or equal to the weight limit.

You need to return the minimum number of boats to carry all persons in the array.

Constraints:

  • 1≤1 \leq people.length ≤5×103\leq 5 \times 10^3

  • 1≤1 \leq people[i] ≤\leq limit ≤3×103\leq 3 \times 10^3

Examples#

Created with Fabric.js 3.6.6 limit 3 Output ? people 2 1 1 Input Output Explanation people = [2, 1, 1]limit = 3There can be only be two people on our boat, and theirtotal weight should be less than or equal to the weightlimit this boat can hold. Sample example 1

1 of 5

Created with Fabric.js 3.6.6 limit 3 Output ? people 2 1 1 Input Output Explanation people = [2, 1, 1]limit = 3The first person jumped to the rescue boat, but we arestill under the weight limit, and can also have one moreperson in our rescue boat. Sample example 1

2 of 5

Created with Fabric.js 3.6.6 limit 3 Output ? people 2 1 1 Input Output Explanation people = [2, 1, 1]limit = 3The second person jumped to the rescue boat, and nowwe have reached the limit of weight and persons theboat can hold. Sample example 1

3 of 5

Created with Fabric.js 3.6.6 limit 3 Output ? people 2 1 1 Input Output Explanation people = [2, 1, 1]limit = 3We got another boat and rescued all of the people onthe sinking ship, and stayed within the condition of weight limit and number of people on the rescueboats. Sample example 1

4 of 5

Created with Fabric.js 3.6.6 limit 3 people 2 1 1 Input Output Explanation Output 2 Sample example 1 people = [2, 1, 1]limit = 3We can only have two people on a single boat, so two boatsare used to rescue the people; hence the output will be theinteger 2.

5 of 5

Understand the problem#

Let’s take a moment to make sure you've correctly understood the problem. The quiz below helps you check if you're solving the correct problem:

Boats To Save People

1

How many boats are required to save everyone if we have the following inputs?

people = [3, 2, 2, 1, 1]

limit = 3

A)

4

B)

3

C)

5

D)

2

Question 1 of 20 attempted

Figure it out#

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Drag and drop the cards to rearrange them in the correct order.

Sort the people array so that the lightest person is at the start of the array and the heaviest person is at the end of the array.

Initialize two pointers— left at the start and right at the end of the array.

Iterate over the people array and check if the combined weight of the lightest and heaviest person is under the weight limit. If it is, then increment the left pointer and decrement the right pointer.

Otherwise, rescue the heaviest person alone and decrement the right pointer.

Increment the number of boats.

Return the number of boats.

Try it yourself#

Implement your solution in main.py of the following coding playground. We've provided a useful code template in the two_pointers.py file, which you may build upon to solve this problem.

Python
main.py
two_pointers.py
Input #1
Input #2
%0 node_01 3 node_11 1 node_21 4 node_31 2 node_41 4
Visualization for Input #1
Boats to Save People

Solution: Jump Game I

Solution: Boats to Save People