Efficient Worker Pairing
Preview mode. Log in to edit, run, submit, and save progress.
Efficient Worker Pairing
A team has an odd number of workers, each with an efficiency rating. Workers must be paired, and the cost of pairing two workers is the absolute difference between their ratings. Since the number of workers is odd, exactly one worker will be left out. Choose which worker to exclude so the total pairing cost of the remaining workers is as small as possible.
Examples
4 2 8 1 9
2
Explanation: Exclude the worker with efficiency 4. The remaining sorted ratings are [1, 2, 8, 9], giving pairs (1,2) and (8,9), with total cost 1 + 1 = 2.
Approach hint
After sorting, the best way to pair an even number of workers is adjacent pairing.
Common mistake
Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.