Lv.1greedysortingtwo-pointers
Rescue Boats
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
People with weights people must be rescued by boats. Each boat carries at most two people whose total weight is at
most limit, and any number of boats may be used. Return the minimum number of boats needed.
Examples
| people | limit | result |
|---|---|---|
[70, 50, 80, 50] | 100 | 3 |
[70, 80, 50] | 100 | 3 |
[30, 40, 50, 60] | 100 | 2 |
Example 3 — (40, 60) and (30, 50).
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(people: int[], limit: int) → int
Constraints
-
people.length -
people[i]limit
Expected complexity
- Time
- O(N log N)
- Space
- O(1)
Examples
| people | limit | Expected |
|---|---|---|
[70,50,80,50] | 100 | 3 |
[70,80,50] | 100 | 3 |
[30,40,50,60] | 100 | 2 |
Hint
Hint
The heaviest person needs a boat anyway, and the best companion is the lightest person: if even they don't fit, nobody does. Sort the weights and move two pointers inwards from both ends. Scanning the remaining people for a partner each time is and exceeds the time limit.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1108 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 11 | verdict only |
| performance | 60 | 3 | verdict only |