Boats to Save People

Minimize the number of boats needed to rescue everyone given a weight limit and a two-person boat capacity.

greedy two-pointers sorting

You are given a list `people` of integers where `people[i]` is the weight of the i-th person, and an integer `limit` representing the maximum weight a boat can carry. Each boat can carry at most two people at the same time, provided the sum of their weights is at most `limit`. It is guaranteed that each person's weight is at most `limit`.

Write a function `num_rescue_boats(people: list[int], limit: int) -> int` that returns the minimum number of boats needed to rescue everyone.

Constraints

- 1 <= len(people) <= 10^5
- 1 <= people[i] <= limit <= 3 * 10^4
- Your solution should run in O(n log n) time and O(n) or O(log n) space.

Example

>>> num_rescue_boats([1,2], 3)
1
>>> num_rescue_boats([3,2,2,1], 3)
3
>>> num_rescue_boats([3,5,3,4], 5)
4

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort the people by weight to pair the heaviest with the lightest.

Use two pointers: one at the start (lightest) and one at the end (heaviest).

If the heaviest can share a boat with the lightest, move both pointers; otherwise, the heaviest goes alone.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.