I got this question during Bloomberg on-site interview this week. Even after solving 170 LeetCode problems, I've never seen a question like this. I wasn't able to solve it and I got rejection right after the inteview. I wonder if anyone have seen this kind of problem and know how to approach it.

Problem

We have houses along a street. Street is divided into block, and each house is located in a single block. We need to allocate k mailboxes to the street in a way that total distance between house and mailboxes are minimum.

The house's locations are given as a list of integer. For example, [3,5,7] means that houses are located in block 3, block 5, block 7. The number of mailboxes to allocate, k, is also given as an input. when k is 2, you need to allocate 2 mailboxes in the street.

Given a list of integers representing the block numbers of houses, and the number of mailbox, determine the minimum total distance from each house to mailbox.

Example 1:

Input: houses = [5, 10, 15, 20], k = 3
Output: 5
Explanation: we can allocate mailbox in block 5, block 10, and somewhere in between 15 and 20, let's say 17.
Then total distance will be (5-5) + (10-10) + (17-15) + (20-17) = 5.

Example 2:

Input: houses = [6, 7, 8, 12], k = 2
Output: 2
Explanation: we can allocate mailbox in block 7, and block 12.
Then total distance will be (7-6) + (7-7) + (8-7) + (12-12) = 2.

Example 3:

input: houses = [3, 5, 6, 8], k = 1
Output: 6
Explanation: If we put mailbox in block 5 or block 6, total distance will be 6.

Example 4:

Input: houses = [8, 12, 17], k = 3
Output: 0
Explanation: Put mailbox in block 8, 12, 17, then total distance will be 0.