Three parcels closest to the pallet limit

Scenario

At a Kestrel Freight hub, some pallets take exactly three parcels. Each pallet has a rated load, and the hub wants every pallet used well. So the loading screen suggests the three waiting parcels whose total weight is closest to the rated load.

The total may be a little under the rated load or a little over it, because the screen only ranks the choices; loaders check the final weight. When two totals are equally close, the hub prefers the lighter one. Parcels can weigh the same, and the waiting list is in no particular order.

Your task

Write closest_total(weights, limit).

weights[i] is the weight of parcel i in grams. The list is in no particular order and may hold equal weights.
limit is the pallet's rated load in grams.
Choose three parcels at three different positions. Return their total weight that is closest to limit, that is, with the smallest |total - limit|.
If two totals are equally close, return the smaller total.
There are always at least three parcels, so an answer always exists.

Examples

Example 1 (traced)#

text2 lines

Input:  weights = [42000, 15000, 31000, 26000, 58000, 9000], limit = 105000
Output: 104000

Sorted, the weights are [9000, 15000, 26000, 31000, 42000, 58000]. The trace works on that sorted copy. best starts at the three lightest parcels, 50000.

i	First parcel	left	right	Total	Distance	best after	Move
0	9000	1	5	82000	23000	82000	too light: left becomes 2
0	9000	2	5	93000	12000	93000	too light: left becomes 3
0	9000	3	5	98000	7000	98000	too light: left becomes 4
0	9000	4	5	109000	4000	109000	too heavy: right becomes 4, the pointers meet
1	15000	2	5	99000	6000	109000	too light: left becomes 3
1	15000	3	5	104000	1000	104000	too light: left becomes 4
1	15000	4	5	115000	10000	104000	too heavy: right becomes 4, the pointers meet
2	26000	3	5	115000	10000	104000	too heavy: right becomes 4
2	26000	3	4	99000	6000	104000	too light: left becomes 4, the pointers meet
3	31000	4	5	131000	26000	104000	too heavy: right becomes 4, the pointers meet

The parcels 15000, 31000 and 58000 make 104000, only 1000 g under the rated load.

Example 2#

text2 lines

Input:  weights = [10000, 20000, 30000, 50000], limit = 70000
Output: 60000

The totals 60000 and 80000 are both 10000 g away from the rated load. The smaller total wins.

Example 3#

text2 lines

Input:  weights = [40000, 50000, 60000], limit = 100000
Output: 150000

Three parcels make only one total. It is above the rated load, and it is still the answer.

Constraints

3 ≤ weights.length ≤ 3,000 (the parcels waiting at one loading bay)
1 ≤ weights[i] ≤ 10^6 (one tonne)
3 ≤ limit ≤ 3 × 10^6

What does n ≤ 3,000 tell you?

Trying every triple of parcels costs n × (n − 1) × (n − 2) / 6 checks. At n = 3,000 that is about 4.5 × 10^9: far over the budget of about 10^8 simple operations a second. An O(n^2) solution makes about 4.5 × 10^6 steps, which fits easily.

Read the values too. The largest total is 3 × 10^6 grams, far below the 32-bit limit, so int is safe for totals and distances.

Scenario

Your task

Write closest_total(weights, limit).

weights[i] is the weight of parcel i in grams. The list is in no particular order and may hold equal weights.
limit is the pallet's rated load in grams.
Choose three parcels at three different positions. Return their total weight that is closest to limit, that is, with the smallest |total - limit|.
If two totals are equally close, return the smaller total.
There are always at least three parcels, so an answer always exists.

Examples

Example 1 (traced)#

text2 lines

Input:  weights = [42000, 15000, 31000, 26000, 58000, 9000], limit = 105000
Output: 104000

Sorted, the weights are [9000, 15000, 26000, 31000, 42000, 58000]. The trace works on that sorted copy. best starts at the three lightest parcels, 50000.

i	First parcel	left	right	Total	Distance	best after	Move
0	9000	1	5	82000	23000	82000	too light: left becomes 2
0	9000	2	5	93000	12000	93000	too light: left becomes 3
0	9000	3	5	98000	7000	98000	too light: left becomes 4
0	9000	4	5	109000	4000	109000	too heavy: right becomes 4, the pointers meet
1	15000	2	5	99000	6000	109000	too light: left becomes 3
1	15000	3	5	104000	1000	104000	too light: left becomes 4
1	15000	4	5	115000	10000	104000	too heavy: right becomes 4, the pointers meet
2	26000	3	5	115000	10000	104000	too heavy: right becomes 4
2	26000	3	4	99000	6000	104000	too light: left becomes 4, the pointers meet
3	31000	4	5	131000	26000	104000	too heavy: right becomes 4, the pointers meet

The parcels 15000, 31000 and 58000 make 104000, only 1000 g under the rated load.

Example 2#

text2 lines

Input:  weights = [10000, 20000, 30000, 50000], limit = 70000
Output: 60000

The totals 60000 and 80000 are both 10000 g away from the rated load. The smaller total wins.

Example 3#

text2 lines

Input:  weights = [40000, 50000, 60000], limit = 100000
Output: 150000

Three parcels make only one total. It is above the rated load, and it is still the answer.

Constraints

3 ≤ weights.length ≤ 3,000 (the parcels waiting at one loading bay)
1 ≤ weights[i] ≤ 10^6 (one tonne)
3 ≤ limit ≤ 3 × 10^6

What does n ≤ 3,000 tell you?

Read the values too. The largest total is 3 × 10^6 grams, far below the 32-bit limit, so int is safe for totals and distances.