Solution: Boats to Save People
Explore how to apply greedy algorithms to optimize boat usage in a rescue scenario. Learn to pair the lightest and heaviest people efficiently under weight constraints to minimize the number of boats required. Understand the problem setup, the naive approach, and how sorting combined with two-pointer technique improves time complexity to O(n log n). This lesson helps you develop skills in solving optimization problems using greedy patterns.
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 ...