Greedy: Assign holes to mice

Problem Statement:

You are given 2 arrays one for mice and one for hole.

There are N mice and N holes and placed in a straight line.

Each hole can have only one mouse.

A mouse can stay in the current position or move one step towards the right or left and each move takes one minute.

You need to assign each mouse a hole, such that, the time taken by last mouse to reach its hole is minimized

Example:

Input: 

Position of mice [4, -4, 2], position of holes [4, 0, 5]

Output: 4 min

Explanation: 

Mouse at position 4, will goto hole position 4, takes 0 min
Mouse at position -4, will goto hole position 0, takes 4 min
Mouse at position 2, will goto hole position 5, takes 3 min
after 4 min all the mice are in the holes

Solution Explanation:

We can solve the problem using greedy approach.

Put every mouse to its nearest hole ti minimize the time.

For that, sort the position of mice and holes and put ith mice in ith hold and keep track of the. maximum distance any mouse has moved.

Time Complexity: O(n)
Space Complexity: O(n.logn)

Code Solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 

int solution(vector<int>& mices, vector<int>& holes) 
{
    int n = mices.size();

    sort(mices.begin(), mices.end());
    sort(holes.begin(), holes.end());
    
    int max = 0; 
    for(int i = 0; i < n; ++i)
    {
        if (max < abs(mices[i] - holes[i]))
            max = abs(mices[i] - holes[i]);
    }
    return max;
}

int main() 
{ 
    vector<int> mices = { 4, -4, 2 };
    vector<int> holes = { 4, 0, 5 };
    
    cout  << solution(mices, holes) << endl;
    
    return 0; 
}

Output

4