A group of hikers has to cross a river. Every raft carries at most two hikers, and the hikers on one raft may weigh at most limit in total. Rafts are single-use: each one crosses once.
Write fewest_rafts(weights: list[int], limit: int) -> int that returns the smallest number of rafts that gets everyone across.
weights[i]is the weight of hikeri. Every hiker weighs at mostlimit, so a raft can always carry one hiker alone.- The order of
weightsmeans nothing: it isn't sorted.
fewest_rafts([70, 50, 80, 50], 100) # 3 (50+50, 70, 80)
fewest_rafts([30, 60, 40, 70], 100) # 2 (30+70, 40+60)
fewest_rafts([20, 90, 95], 100) # 3
fewest_rafts([5], 5) # 1
Constraints: 1 <= len(weights) <= 2 * 10^5; 1 <= weights[i] <= limit <= 10^9.
Aim for O(n log n). Searching the remaining hikers for a partner each time is O(n²) and too slow at this size.
Show hint
think about the heaviest hiker first. Who is the best partner for them, if anyone can share their raft at all?