Assign Mice to Holes

Assign Mice to Holes is a clean greedy problem. It looks like an assignment puzzle, but a single sort collapses it into a one-line scan.

The slow way first

The brute-force view is an assignment problem: try every way to match mice to holes (there are n! of them), compute the slowest mouse for each matching, and keep the smallest. That is O(n! · n) — hopeless beyond a handful of mice.

The question to ask: can two mice ever benefit from crossing paths? If a left mouse takes a right hole while a right mouse takes a left hole, their paths cross, and uncrossing them never makes the worse traveler worse. That hint points straight at sorting.

The idea: sort, then pair in order

Sort the mice and sort the holes. Then send the i-th smallest mouse to the i-th smallest hole. No crossings, no cleverness. The total time is decided by the slowest mouse, so the answer is the largest |mice[i] - holes[i]| across all paired columns.

Why is the sorted pairing optimal? An exchange argument: if a matching ever has two pairs that cross (a smaller mouse going to a larger hole than a larger mouse), swapping their holes cannot increase the maximum distance. Repeating that removes every crossing, leaving the sorted pairing.

Walk through it

Step through the animation. First both rows sort. Then the pointer i sweeps left to right, pairing the i-th mouse with the i-th hole and showing each column distance. The running answer keeps the biggest distance seen so far — here it locks in at 4 on the very first pair.

Pseudocode

sort mice ascending
sort holes ascending
answer = 0
for i from 0 to n - 1:
    answer = max(answer, |mice[i] - holes[i]|)
return answer

The Python solution

def assign_mice(mice, holes):
    # both lists have the same length
    mice.sort()
    holes.sort()
    answer = 0
    for i in range(len(mice)):
        answer = max(answer, abs(mice[i] - holes[i]))
    return answer

• We sort mice and holes independently — each in O(n log n).
• After sorting, position i in each list lines up: the i-th mouse pairs with the i-th hole.
• abs(mice[i] - holes[i]) is the travel distance for that one pair.
• answer tracks the maximum distance, because the last mouse to settle decides the total time.
• We never need an explicit matching structure — the index i is the matching.

Complexity

The sort is the whole cost. The pairing scan is O(n) and the extra space is O(1) if we sort in place. Sorting turns an exponential search into a linear sweep.

When this pattern shows up

Practice