Parcel Lockers Along a Road

Hard

Houses stand along a straight road, and homes[i] is the position of house i (all positions are different). You need to place lockers parcel lockers on the road, at any points you like. Each household walks to its nearest locker. Place the lockers so that the total distance from every house to its nearest locker is as small as possible, and return that total.

Example 1

homes=[2, 7, 9, 15], lockers=2 → 7

Put one locker at house 7: residents of 2, 7 and 9 walk 5 + 0 + 2 = 7. Put the other at house 15, where nobody walks. The total is 7.

Example 2

homes=[6, 1, 3], lockers=3 → 0

There are as many lockers as houses, so each house gets its own.

Example 3

homes=[1, 10, 20, 40, 41], lockers=2 → 20

Constraints

1 ≤ lockers ≤ len(homes) ≤ 100
1 ≤ homes[i] ≤ 10⁴
All homes[i] are distinct

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Math Dynamic Programming Sorting

Similar problems

Biggest Number Divisible by Three Hard Total Strength of All Squads Hard Chain of Multiples Medium Picks Without a Fixed Gap Medium Sets Without a Fixed Gap Medium

Input

homes=[2, 7, 9, 15], lockers=2

Expected

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