Boats to Save People

The key idea

Sort the people, then pair the lightest with the heaviest. If the heaviest person can share with the lightest remaining person, send them together; otherwise the heaviest must ride alone. Either way the heaviest person is now seated, so move the right pointer inward. A boat is never wasted, because no greedier pairing exists for the heaviest person than the lightest available partner.

Problem

You are given an array people where people[i] is the weight of the i-th person, and an integer limit.

Each boat carries at most 2 people at the same time, provided the sum of their weights is at most limit.

Return the minimum number of boats to carry every given person.

Constraints

1 <= people.length <= 50000
1 <= people[i] <= limit <= 30000
It is guaranteed each person can be carried by a boat.

Examples

Input: people = [1,2], limit = 3 Output: 1

Input: people = [3,2,2,1], limit = 3 Output: 3

Input: people = [3,5,3,4], limit = 5 Output: 4

Complexity

Time: O(n log n) Space: O(1)

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →