Solution: Boats to Save People
Let's solve the Boats to Save People problem using the Greedy pattern.
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 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:
-
people.length
-
people[i]
limit
Solution
You may have already, brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and implementation constraints.
Naive approach
The naive approach is to use a nested loop. For each person, we can check all the remaining people to see if they can form a pair that fits into a boat. If we find a pair, we’ll remove them from the array, increment the number of boats used, and move to the next person. If we can’t find a pair for a person, we put them in a boat alone and increment the number of boats used. We repeat this process until all people are rescued.
The time complexity of this approach is , since we’ll use the nested loop to make pairs.
Optimized approach using the Greedy pattern
To solve the problem, we can use the greedy pattern and pair people with the lightest and heaviest people available, as long as their combined weight does not exceed the weight limit. If the combined weight exceeds the limit, we can only send one person on that boat. This approach ensures that we use the minimum number of boats to rescue the people.
The steps to implement the approach above are given below:
-
Sort the
people
array in ascending order so that the lightest person is at the start of the array, and the heaviest person is at the end. -
Initialize two pointers,
left
andright
. Theleft
pointer points to the lightest person at the start of the array, and theright
pointer points to the heaviest person at the end of the array. Next, a variable,boats
, is initialized to0
, representing the number of boats used. -
Iterate over the
people
array until theleft
pointer is greater than theright
pointer. This means that all people have been rescued. Perform the following steps in each iteration of the loop-
Check if both the lightest and heaviest persons can fit in one boat, i.e.,
people[left] + people[right]
is less than or equal tolimit
. If they can fit, theleft
pointer is incremented and theright
pointer is decremented. -
If they cannot fit in one boat, the heaviest person is rescued alone, and the
right
pointer is decremented. -
The
boats
variable is incremented by1
, representing the number of boats used.
-
-
Return the minimum number of boats required to rescue all the people.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.