AssignMiceToHole.cpp

/*
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
*/

// Sort both distance, in order to minimise the maxima, each mice should go to its neighbour Hole only.

int Solution::mice(vector<int> &A, vector<int> &B)
{
    int max_total = INT_MIN;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    for (int i = 0; i < A.size(); i++)
    {
        int max_till = std::abs(A[i] - B[i]);
        if (max_till > max_total)
            max_total = max_till;
    }

    return max_total;
}