A fulfillment center is retooling its floor plan. Along a single guide rail there are n numbered docking bays and n autonomous robots, both positioned somewhere along the rail (given as integer coordinates). Every robot must end up parked in exactly one bay, with no two robots sharing a bay, and moving a robot one unit along the rail costs exactly one unit of energy. The floor manager wants to choose which robot goes to which bay so that the total energy spent moving every robot into a bay is as small as possible.
Given the bay positions and the robot positions, determine the minimum total number of unit moves needed to get every robot into some bay, one robot per bay.
Line 1: a single integer n, the number of docking bays (equal to the number of robots). Line 2: n space-separated integers, the positions of the docking bays along the rail. Line 3: n space-separated integers, the positions of the robots along the rail.
A single integer: the minimum total number of unit moves required.
Example 1
Input
4 4 1 6 2 1 7 3 3
Expected
3
Explanation
Sorted bay positions are [1,2,4,6] and sorted robot positions are [1,3,3,7]. Pairing the i-th smallest bay with the i-th smallest robot gives moves 0,1,1,1, totaling 3, which is optimal.
Example 2
Input
2 10 20 15 15
Expected
10
Explanation
Both robots sit at position 15, and the bays are at 10 and 20. Whichever robot is sent to bay 10 travels 5 units and the other travels 5 units to bay 20, so the total is always 10.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →