Allocate Mailboxes
Given the array houses where houses[i] is the location of the i^th house along a street and an integer k, allocate k mailboxes in the street.
Return the minimum total distance between each house and its nearest mailbox.
The test cases are generated so that the answer fits in a 32-bit integer.
Example 1
Input
houses = [1,4,8,10,20], k = 3Output
5Allocate mailboxes in positions 3, 9, and 20 for a minimum total distance of |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5.
Example 2
Input
houses = [2,3,5,12,18], k = 2Output
9Allocate mailboxes in positions 3 and 14 for a minimum total distance of |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.
Constraints
- 1 <= k <= houses.length <= 100
- 1 <= houses[i] <= 10^4
- All the integers of
housesare unique.