Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

Solution: Boats to Save People

Explore how to apply a greedy algorithm to efficiently solve the problem of rescuing people using the fewest boats possible. Learn to pair the lightest and heaviest individuals based on weight limits and implement an optimized approach to minimize boats used. This lesson covers sorting, two-pointer techniques, and analyzing time and space complexity.

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 ...