A warehouse packs boxes into crates. Every crate holds at most two boxes, and the boxes in a crate must weigh at most limit in total. Given a list weights (each weights[i] <= limit), return the minimum number of crates needed to pack every box.
Examples
Input: weights = [3, 2, 2, 1], limit = 3
Output: 3
Explanation: crates {1, 2}, {2}, {3}.
Input: weights = [3, 5, 3, 4], limit = 5
Output: 4
Explanation: no two boxes fit together.
Constraints
0 <= len(weights) <= 10**51 <= weights[i] <= limit <= 10**6- Target: O(n log n) time (sorting), then a single O(n) scan.
Goals
- Pair the heaviest remaining item with the lightest when possible
- Prove to yourself why the greedy pairing is never worse