-
Notifications
You must be signed in to change notification settings - Fork 0
/
mice_to_holes.py
33 lines (25 loc) · 1.03 KB
/
mice_to_holes.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
"""
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.
"""
def mice_to_holes(mice, holes):
mice.sort()
holes.sort()
max_time = 0
for i, mouse in enumerate(mice):
max_time = max(max_time, abs(mouse - holes[i]))
return max_time
print mice_to_holes([-4, 2, 4], [0, 4, 5])