143. Rescue Rafts
After a flood, a rescue team must carry every stranded person across a river. The array weights gives the weight of each person, and every raft can carry at most limit in total weight.
A raft holds at most two people at the same time, and the combined weight of the people on it must not exceed limit. Every person weighs at most limit, so everyone can be carried, at least on a raft of their own. Return the minimum number of rafts needed to carry all the people across.
Example 1
- Input:
- weights = [70,50,80,50], limit = 100
- Output:
- 3
- Explanation:
The two 50s can share a raft (total 100). Pairing 70 or 80 with anyone exceeds 100, so they travel alone: (50,50), (70), (80) uses 3 rafts.
Example 2
- Input:
- weights = [3,5,3,4], limit = 5
- Output:
- 4
- Explanation:
Each pair of people exceeds 5 (3+3=6, 3+4=7, ...), so everyone needs a raft: 4.
Example 3
- Input:
- weights = [1,2,2,3], limit = 3
- Output:
- 3
- Explanation:
Only 1 can be paired (1+2=3 fits; 1+3=4 and 2+2=4 do not). The best plan is (1,2), (2), (3), so 3 rafts.
Constraints
1 ≤ weights.length ≤ 105
1 ≤ weights[i] ≤ limit ≤ 3 * 104
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 4,000 msC++ 1,000 msJava 2,000 msJavaScript 2,000 msTypeScript 2,000 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(1) extra