How can we approach the problem when no_holes > no_mices


#1

How can we approach the problem when no_holes > no_mices


#2

Assign each mouse to its closest hole in a merge-sort like fashion(let i be the mice index and j be the holes index), update i only if the hole[j] is closer to mouse[i] than hole[j+1], else just update j, store all the matches in an array(matches array). In the end if you did not manage to assign all the mice to a hole, pad the ans to fit(go through the matches array until the number of remaining slots for mouse is smaller than the number of holes left and update all the matches from here onwards).


#3

you can do this. I hope you understand the code. Let n be number of mice and m be number of holes. Sort the positions of mice and holes. For obvious reasons we will get minimum time if we select n consecutive holes for n mice. Now you just have select which n consecutive holes will give minimum time. You can check it one by one as given in the code below:

int Solution::mice(vector<int> &A, vector<int> &B) {
sort(A.begin(), A.end());
sort(B.begin(), B.end());
int result=1000000;
for(int i=0; i<B.size()-A.size()+1; i++)
{
    int thisone=0;
    for(int j=0; j<A.size(); j++)
    {
        thisone=max(thisone, abs(A[j]-B[i+j]));
    }
    if(thisone<result)
    {
        result=thisone;
    }
}
return result;

}


#4

Can you give a formal proof as to why will we get the correct answer if consecutive holes are selected? I am also getting the intuition but it may well not be correct


#5

Not sure if its a formal proof but a simple explanation of the same would be that if you skip a hole, the mouse would have to go farther away that he would have for that hole and same for the next mouse and so on since the array is sorted the next hole ( number ) would always be farther away from the first choice ( at the same index ).


#6

For e.g
holes position: 1, 2, 3, 4, 5
mice position: 1, 3, 5

Now to get the minimum time, we cant pick the consecutive holes, because minimum time we can get here is 0, but if we pic consecutive holes then time we get is equal to 2, 1, 2.


#7

start from the end after sorting both the vectors. Mice at position 5 will first go to position 5 and movement will be 1 then try to put the same at position 4 but now we got movement greater than we we had (0) so stop. Do the same for mice at pos 3. Try for pos 4(move=1), pos 3(move =0), pos 2(move = 1, increased from last movement, so stop). Do the same for mice at pos 1. Also check if we have enough position left for the remaining mice while searching for appropriate pos from right to left.


#8

` public int mice_moreNoOfHoles(int[] positions, int[] holes) {
int time = 0;

    Arrays.sort(positions);
    Arrays.sort(holes);

    int noOfMice = positions.length;
    int noOfHoles = holes.length;

    HashMap<Integer, Integer> map = new HashMap<>();

    for (int i = 0, j = 0; i < noOfHoles && j < noOfMice; i++) {
        //FOR BEST HOLES, THERE ARE 3 possibilities
        //1. THE MOUSE DOESN'T HAVE TO MOVE
        //2. THE NEXT HOLE IS FARTHER TO THE MOUSE THAN THIS HOLE
        //3. THE MOUSE DOES NOT HAVE A CHOICE AND ALL HOLES HAVE TO FILLED UP FROM THE CURRENT HOLE TO ACCOMODATE ALL MICE
        if ((positions[j] == holes[i]) || ((i + 1 < holes.length) && (Math.abs(positions[j] - holes[i + 1]) > Math.abs(positions[j] - holes[i + 1]))) || (noOfHoles - i <= noOfMice)) {
            int timeTimeToGetToPosition = Math.abs(positions[j] - holes[i]);
            if (timeTimeToGetToPosition > time) time = timeTimeToGetToPosition;
            map.put(positions[j],holes[i]);
            j++;
        }
    }

    return time;
}`