Assign Mice to Holes

There are N Mice and N holes placed in a straight line. Each hole can accommodate 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 consume 1 minute.

Assign mice to holes so that the time when the last mouse gets inside a hole is minimized.

For example, Let the positions of mice are: 4 -4 2
positions of holes are: 4 0 5

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

Note that this may not be the only solution. With the same answer (4 min), there may exist multiple solutions. Another solution is as below:

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

Solution:

This problem can be solved using a Greedy Approach.

We put every mouse to its nearest hole to minimize the time. To do this, sort the positions of mice and holes and put the i^th mice in the i^th hole in the holes list.

While moving the mouse, keep a track of the maximum distance any mouse have moved.

Code:

int miceInHole(int[] m, int[] h) 
{ 
   if (m.length != h.length) // ERROR CONDITION
      return -1; 
  
   Arrays.sort(mice); 
   Arrays.sort(holes); 
  
   int n = m.length; 
  
   int max = 0; 
   for (int i=0; i<n; i++) 
      if (max < Math.abs(m.get(i) - h.get(i))) 
         max = Math.abs(m.get(i) - h.get(i)); 
  
   return Math.abs(max); 
}

Time Complexities:

This code will take O(n) time if the arrays are sorted in ascending order. But since we are also sorting the array inside the function, it will take O(n.lg(n)) time.