Show problems as
Classic problem #881MediumArrayTwo PointersGreedySortingTimsort

Boats to Save People

Real-world version: Gondola Cabins for the Ski Queue
Tracked in this browser only
Read Boats to Save People on LeetCode(opens in a new tab)

The statement here is our own: the same inputs, outputs and technique.

A ski lift sends up cabins that seat at most two riders each, and a cabin may carry at most limit kilograms of rider weight in total. riders[i] is the weight in kilograms of the i-th person waiting, given in no particular order.

Everyone in the queue has to get up the mountain, and riders may be seated in any grouping you like as long as both cabin rules hold. Return the smallest number of cabins that will carry the whole queue.

No single rider ever exceeds limit, so the queue can always be cleared.

Examples

Example 1

Input
riders = [9, 2, 8, 3, 7, 4], limit = 11
Output
3

Seating 2 with 9, 3 with 8 and 4 with 7 fills three cabins at 11 kg each, which seats all six riders inside both rules.

Example 2

Input
riders = [3, 4, 5], limit = 9
Output
2

One cabin takes 3 and 5 for 8 kg and the next takes 4 on its own.

Example 3

Input
riders = [1, 1, 1, 1], limit = 4
Output
2

A cabin seats two riders however light they are, so the four riders fill two cabins carrying 2 kg each.

Constraints

  • 1 <= riders.length <= 5 * 10^4
  • 1 <= riders[i] <= limit <= 3 * 10^4

The signature

The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.

Python
def gondola_cabin_count(riders: list[int], limit: int) -> int:
Java
public int gondolaCabinCount(int[] riders, int limit)

More on the same topics