After a flood, people with weights weights wait to be ferried. Each raft carries at most two people whose total weight is at most limit. Every person weighs at most limit. Return the minimum number of rafts needed.
Examples
Input: weights = [70, 50, 80, 50], limit = 100
Output: 3
Explanation: (50, 50), (70), (80).
Input: weights = [30, 60, 40, 70], limit = 100
Output: 2
Explanation: (30, 70) and (40, 60).
Constraints
0 <= len(weights) <= 10**5,1 <= weights[i] <= limit <= 3 * 10**4.- Target complexity: O(n log n).
Goals
- Sort weights so the heaviest and lightest can be paired
- Justify always sending the heaviest person on the next raft
- Count rafts with two pointers in linear time after sorting