Fewest cargo bikes for the round

Scenario

In city centres, Kestrel Freight delivers small parcels by cargo bike. Each bike carries at most two parcels, and their total weight must stay within the bike's load limit. Every bike in a round has the same limit, and no single parcel is heavier than that limit.

Before each round, dispatch knows the weight of every parcel. Bikes and riders are limited, so dispatch wants to send as few bikes as possible. Your job is to compute that number.

Your task

Write fewest_bikes(weights, limit).

weights[i] is the weight of parcel i in grams. The list is in no particular order.
limit is the load limit of one bike in grams. Every weight is at most limit.
A bike carries one parcel, or two parcels whose weights add up to at most limit.
Return the fewest bikes that carry every parcel.

Examples

Example 1 (traced)#

text2 lines

Input:  weights = [14000, 23000, 5000, 28000, 11000, 20000, 8000, 16000], limit = 30000
Output: 5

Sorted, the weights are [5000, 8000, 11000, 14000, 16000, 20000, 23000, 28000]. Each row loads one bike: the heaviest waiting parcel, plus the lightest one if it fits.

left	right	Lightest	Heaviest	Total	Lightest rides along?	Bikes
0	7	5000	28000	33000	no	1
0	6	5000	23000	28000	yes	2
1	5	8000	20000	28000	yes	3
2	4	11000	16000	27000	yes	4
3	3	14000	14000	one parcel	no	5

The 28000 g parcel does not fit even with the lightest parcel, so it rides alone. The 14000 g parcel is the last one waiting, so it rides alone too.

Example 2#

text2 lines

Input:  weights = [6000, 5000, 4000, 5000], limit = 10000
Output: 2

The bikes take 6000 + 4000 and 5000 + 5000, each exactly on the limit. Pairing the two lightest parcels first, 4000 + 5000, leaves 5000 and 6000, which do not fit together: 3 bikes.

Example 3#

text2 lines

Input:  weights = [18000], limit = 20000
Output: 1

One parcel needs one bike.

Constraints

1 ≤ weights.length ≤ 10^5
1 ≤ weights[i] ≤ 3 × 10^5
1 ≤ limit ≤ 3 × 10^5, and weights[i] ≤ limit for every i

What does n ≤ 10^5 tell you?

A first attempt that scans the waiting parcels for each bike can make n × (n − 1) / 2 steps: about 5 × 10^9 at n = 10^5. That is far over the budget of about 10^8 simple operations a second.

Sorting costs about n log n, roughly 1.7 × 10^6 steps. One pass after the sort fits easily, so aim for O(n log n). Two weights add up to at most 6 × 10^5, so 32-bit integers are enough.

Scenario

Before each round, dispatch knows the weight of every parcel. Bikes and riders are limited, so dispatch wants to send as few bikes as possible. Your job is to compute that number.

Your task

Write fewest_bikes(weights, limit).

weights[i] is the weight of parcel i in grams. The list is in no particular order.
limit is the load limit of one bike in grams. Every weight is at most limit.
A bike carries one parcel, or two parcels whose weights add up to at most limit.
Return the fewest bikes that carry every parcel.

Examples

Example 1 (traced)#

text2 lines

Input:  weights = [14000, 23000, 5000, 28000, 11000, 20000, 8000, 16000], limit = 30000
Output: 5

Sorted, the weights are [5000, 8000, 11000, 14000, 16000, 20000, 23000, 28000]. Each row loads one bike: the heaviest waiting parcel, plus the lightest one if it fits.

left	right	Lightest	Heaviest	Total	Lightest rides along?	Bikes
0	7	5000	28000	33000	no	1
0	6	5000	23000	28000	yes	2
1	5	8000	20000	28000	yes	3
2	4	11000	16000	27000	yes	4
3	3	14000	14000	one parcel	no	5

The 28000 g parcel does not fit even with the lightest parcel, so it rides alone. The 14000 g parcel is the last one waiting, so it rides alone too.

Example 2#

text2 lines

Input:  weights = [6000, 5000, 4000, 5000], limit = 10000
Output: 2

The bikes take 6000 + 4000 and 5000 + 5000, each exactly on the limit. Pairing the two lightest parcels first, 4000 + 5000, leaves 5000 and 6000, which do not fit together: 3 bikes.

Example 3#

text2 lines

Input:  weights = [18000], limit = 20000
Output: 1

One parcel needs one bike.

Constraints

1 ≤ weights.length ≤ 10^5
1 ≤ weights[i] ≤ 3 × 10^5
1 ≤ limit ≤ 3 × 10^5, and weights[i] ≤ limit for every i

What does n ≤ 10^5 tell you?

A first attempt that scans the waiting parcels for each bike can make n × (n − 1) / 2 steps: about 5 × 10^9 at n = 10^5. That is far over the budget of about 10^8 simple operations a second.

Sorting costs about n log n, roughly 1.7 × 10^6 steps. One pass after the sort fits easily, so aim for O(n log n). Two weights add up to at most 6 × 10^5, so 32-bit integers are enough.