DSA problem
Boats to Save People
You are given an array people where people[i] is the weight of the i-th person, and an integer limit which is the maximum weight a single boat can carry. Each boat carries at most two people at the same time provided the sum of their weights is at most limit. Return the minimum number of boats required to carry every given person.
The pairing constraint — at most two people per boat — is what makes this a greedy problem rather than a packing problem. Because no boat can hold three or more, the only question is who shares a boat with whom. A natural strategy is to pair the heaviest unpaired person with the lightest unpaired person whenever they fit, otherwise send the heaviest alone.
To turn that idea into a clean algorithm, sort the array and use two pointers, left at the lightest and right at the heaviest. If people[left] + people[right] <= limit, both can share a boat: advance left and decrement right. Otherwise the heaviest must go solo: decrement right only. Each iteration uses one boat, and the loop ends when the pointers cross.
This greedy is optimal by an exchange argument: if an optimal solution pairs the heaviest person H with someone L' instead of the lightest L, we can swap L' and L without making the schedule worse — the heaviest paired with the lightest possible companion never wastes capacity. The whole algorithm runs in O(n log n) time (sort) and O(1) extra space.
Examples
people = [1,2], limit = 31people = [3,2,2,1], limit = 33people = [3,5,3,4], limit = 54Constraints
- 1 <= people.length <= 5 * 10^4
- 1 <= people[i] <= limit <= 3 * 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.