Funcia
Lv.1greedysortingtwo-pointers

Rescue Boats

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

peoplelimitresult
[70, 50, 80, 50]1003
[70, 80, 50]1003
[30, 40, 50, 60]1002

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

  • 1≤1 \le people.length ≤200,000\le 200{,}000
  • 1≤1 \le people[i] ≤\le limit ≤1,000,000\le 1{,}000{,}000

Expected complexity

Time
O(N log N)
Space
O(1)

Examples

peoplelimitExpected
[70,50,80,50]1003
[70,80,50]1003
[30,40,50,60]1002

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 O(N2)O(N^2) and exceeds the time limit.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251108 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4011verdict only
performance603verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.