Greedy Algorithms8 sections · 316 units
Open in Course

Problem - Boats to Save People

Pair heavy with light

People have weights. Each boat has a limit and holds at most 22 people. Minimize boats used.

Example: people = [3,2,2,1], limit = 33. Boats: (1,2), (22), (33). Total: 33 boats. What is the greedy pairing strategy? Constraint: n5×104n \le 5 \times 10^4 and you need O(nlogn)O(n \log n) time using O(1)O(1) space sorting. Naive assignment without sorting can waste boat capacity and use more boats than necessary.