Minimum House-to-Mailbox Distance with k Mailboxes

### Problem Houses occupy distinct positions along a street. Place k mailboxes to minimize the sum,over all houses,of the distance to that house's nearest mailbox. Return this minimum total distance; mailbox positions themselves are not returned. ```cpp class Solution { public: int minDistance(vector<int>& houses, int k); }; ``` ### Examples **Example 1:** ```text Input: houses = [1,3,10], k = 2 Output: 2 Explanation: Serve1 and3 with a mailbox anywhere between them,and put another at10. The alternative adjacent pair3,10 costs7,so2 is optimal. ``` **Example 2:** ```text Input: houses = [9,1,5], k = 3 Output: 0 Explanation: Place one mailbox at every house. ``` ### Constraints - `1 <= k <= houses.length <= 100`. - Every house position is a unique integer in `[1,10000]`. - The minimum answer fits a 32-bit integer. ### Contract considerations Each house uses its nearest mailbox; k<=n permits a zero answer when k=n. ```hint Read the boundary condition Use every house's nearest mailbox when measuring cost. Include unordered house input and the case of one mailbox per house. ``` ### Boundary reminders Each house uses its nearest mailbox; k<=n permits a zero answer when k=n.