Pair Up for the Lightest Heavy Bundle

Medium

Movers carry boxes two at a time: every two boxes are tied into one bundle. You are given an array weights of even length holding the box weights. Split all boxes into pairs so that every box belongs to exactly one pair. The weight of a bundle is the sum of its two boxes. You want the heaviest bundle to be as light as possible. Return its weight under the best pairing.

Example 1

weights=[4, 1, 7, 6] → 10

Pairs (1, 7) and (4, 6) give sums 8 and 10. Putting 6 and 7 together would give 13, which is worse. The answer is 10.

Example 2

weights=[5, 5, 2, 8, 3, 7] → 10

Pairs (2, 8), (3, 7) and (5, 5) all sum to 10.

Example 3

weights=[9, 9] → 18

Constraints

2 ≤ len(weights) ≤ 10⁵
len(weights) is even
1 ≤ weights[i] ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy Array Two Pointers Sorting

Similar problems

Studios for Recording Sessions Medium Fix the Middle of the Line Medium Stick Triples That Form a Triangle Medium Best-Paid Gig for Each Worker Medium Lining Up Against Rivals Medium

Input

weights=[4, 1, 7, 6]

Expected

Run checks the first 3 tests in your browser. Submit checks all 96 tests on the server, hidden ones included.