Boats to Save People – Two Pointer

Pair the heaviest with the lightest to minimize the number of rescue boats.

two-pointers sorting greedy arrays

You are given an array `people` 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 does not exceed `limit`. It is guaranteed that every person can be carried by a boat (i.e., `people[i] <= limit`).

Write a function `num_rescue_boats(people, limit)` that returns the minimum number of boats needed to rescue everyone.

### Function Signature
```python
def num_rescue_boats(people: list[int], limit: int) -> int:
```

### Notes
- You may reorder the people as you like.
- The function should be efficient for lists up to length 50,000.

Constraints

1 <= len(people) <= 50,000
1 <= people[i] <= limit <= 30,000
Expected time complexity: O(n log n), space O(1) extra (ignoring input storage).

Example

```python
>>> 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 ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sorting the array helps: try pairing the heaviest person with the lightest possible companion.

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

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

Count the boats as you move the pointers; stop when the pointers cross.

Test Results

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