Press "Enter" to skip to content

花花酱 LeetCode 1478. Allocate Mailboxes

Given the array houses and an integer k. where houses[i] is the location of the ith house along a street, your task is to allocate k mailboxes in the street.

Return the minimum total distance between each house and its nearest mailbox.

The answer is guaranteed to fit in a 32-bit signed integer.

Example 1:

Input: houses = [1,4,8,10,20], k = 3
Output: 5
Explanation: Allocate mailboxes in position 3, 9 and 20.
Minimum total distance from each houses to nearest mailboxes is |3-1| + |4-3| + |9-8| + |10-9| + |20-20| = 5 

Example 2:

Input: houses = [2,3,5,12,18], k = 2
Output: 9
Explanation: Allocate mailboxes in position 3 and 14.
Minimum total distance from each houses to nearest mailboxes is |2-3| + |3-3| + |5-3| + |12-14| + |18-14| = 9.

Example 3:

Input: houses = [7,4,6,1], k = 1
Output: 8

Example 4:

Input: houses = [3,6,14,10], k = 4
Output: 0

Constraints:

  • n == houses.length
  • 1 <= n <= 100
  • 1 <= houses[i] <= 10^4
  • 1 <= k <= n
  • Array houses contain unique integers.

Solution: DP

First, we need to sort the houses by their location.

This is a partitioning problem, e.g. optimal solution to partition first N houses into K groups. (allocating K mailboxes for the first N houses).

The key of this problem is to solve a base case, optimally allocating one mailbox for houses[i~j], The intuition is to put the mailbox in the middle location, this only works if there are only tow houses, or all the houses are evenly distributed. The correct location is the “median position” of a set of houses. For example, if the sorted locations are [1,2,3,100], the average will be 26 which costs 146 while the median is 2, and the cost becomes 100.

dp[i][k] := min cost to allocate k mailboxes houses[0~i].

base cases:

  1. dp[i][1] = cost(0, i), min cost to allocate one mailbox.
  2. dp[i][k] = 0 if k > i, more mailboxes than houses. // this is actually a pruning.

transition:

dp[i][k] = min(dp[p][k-1] + cost(p + 1, i)) 0 <= p < i,

allocate k-1 mailboxes for houses[0~p], and allocate one for houses[p+1~i]

ans:

dp[n-1][k]

Time complexity: O(n^3)
Space complexity: O(n^2) -> O(n)

C++

O(1) time to compute cost. O(n) Time and space for pre-processing.

C++

请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.

Buy anything from Amazon to support our website
您可以通过在亚马逊上购物(任意商品)来支持我们

Paypal
Venmo
huahualeetcode
微信打赏

Be First to Comment

Leave a Reply