Boats to Save People
Medium · Two Pointers · Array · Two Pointers · Greedy · Sorting
Problem
You are given an array people, where people[i] is the weight of person i, and an integer limit. There are as many boats as you need; each boat carries at most two people whose combined weight is at most limit.
Return the minimum number of boats needed to carry everyone. Every person weighs no more than limit, so anyone can ride alone.
Examples
Input: people = [4,2,3,5], limit = 6 Output: 3
Pair 2 with 4; then 3 and 5 cannot share (8 > 6), so each needs its own boat.
Input: people = [1,2], limit = 3 Output: 1
Both fit together exactly at the limit.
Input: people = [5,5,5], limit = 5 Output: 3
No two people can share a boat.
Constraints
- 1 <= len(people) <= 5 · 10^4
- 1 <= people[i] <= limit <= 3 · 10^4
Approaches
- Heaviest first, scan for the heaviest partner who fits — time O(n²), space O(n)
Follow-up
What if a boat could carry any number of people up to the weight limit? Then it becomes bin packing, which is NP-hard: no simple greedy is always optimal. The two-person cap is what makes heaviest-with-lightest exact.
Related problems
Start free on Cariara · Coding problems · System design studio
