Source: Assign Mice to Holes

There are N Mice and N holes are placed in a straight line.
Each hole can accomodate only 1 mouse.
A mouse can stay at his position, move one step right from x to x + 1, or move one step left from x to x − 1. Any of these moves consumes 1 minute.
Assign mice to holes so that the time when the last mouse gets inside a hole is minimized.

Example:

positions of mice are:
4 -4 2
positions of holes are:
4 0 5

Assign mouse at position x=4 to hole at position x=4 : Time taken is 0 minutes 
Assign mouse at position x=-4 to hole at position x=0 : Time taken is 4 minutes 
Assign mouse at position x=2 to hole at position x=5 : Time taken is 3 minutes 
After 4 minutes all of the mice are in the holes.

Since, there is no combination possible where the last mouse's time is less than 4, 
answer = 4.

Input:

A :  list of positions of mice
B :  list of positions of holes

Output:

single integer value 

NOTE: The final answer will fit in a 32 bit signed integer.

解題：

解這題不用太費心思考怎麼做才能最佳化。在這題我們需要輸出的資料是將所有老鼠分配到每個指定洞穴的總移動距離，因此個別鼠與洞的關係是否被最佳化其實不是我們要思考的問題；事實上，在移除位置完全符合的鼠／洞組合後，對剩餘資料進行排序計算得出之總移動距離，會與直接進行排序分配之總移動距離相等。舉例說明：

M: [ -100, 0, -50, 100, 70, 11] -> -100, -50, 11, 50, 70, 100
H: [ 0, 50, 30, -20, -50, -11]  -> -50, -20, -11, 0, 30, 50
優先鎖定最佳化（移動距離為 0 ），總移動距離為：
50 + 30 + 22 + 70 + 70 + 0 = 242
依資料排序進行移動，總移動距離為：
50 + 30 + 50 + 40 + 50 = 242

因此，在解題時也完全無須費心將已最佳化之鼠洞組合找出，直接採用排序並計算距離即可。

class Solution:
    # @param M : list of integers, positions of mice
    # @param H : list of integers, positions of Holes
    # @return an integer
    def mice(self, M, H):
        #Think we can just apply sorting?!
        M.sort()
        H.sort()
        n = len(M)
        minMins = 0
        for i in range(n):
            if abs(M[i] - H[i]) > minMins:
                minMins = abs(M[i] - H[i])
        return minMins

GitHub: GitHub

發表留言