10173. Mice and holes

There are n mice and n holes on a straight line. Each hole can only accommodate 1 mouse. A mouse can stay in its place, move one step to the right from x to x + 1, or move one step to the left from x to x – 1. Any of these moves takes 1 minute. Assign mice to holes so that the time when the last mouse hides in a hole is minimized.

Input. The first line contains the number n (n ≤ 10⁵). The second line contains the positions of n mice. The third line contains the positions of n holes. The positions of mice and holes are integers from 0 to 10⁹.

Output. Print the minimum time it takes for the last mouse to hide in a hole.

Sample input	Sample output
4 3 6 1 9 5 3 11 2	2

SOLUTION

greedy

Algorithm analysis

Sort the coordinates of mice and holes accordingly in arrays a and b. Mouse a[i] should hide in hole b[i]. Compute the maximum among the differences of absolute values | b[i] – a[i] |.

Example

Sort arrays with coordinates of mice and holes. Assign mice a[i] to the hole b[i].

The answer 2 is achieved for the fourth mouse, which should run from the point with coordinate 9 to the hole with coordinate 11.

Algorithm realization

Declare the arrays a and b.

#define MAX 100001

int a[MAX], b[MAX];

Read the input data.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &a[i]);

for (i = 0; i < n; i++)

scanf("%d", &b[i]);

Sort the arrays.

sort(a, a + n);

sort(b, b + n);

Compute the maximum differences among the absolute values of | b[i] – a[i] |.

res = 0;

for (i = 0; i < n; i++)

if (abs(b[i] - a[i]) > res) res = abs(b[i] - a[i]);

Print the answer.

printf("%d\n", res);

Java realization

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

Integer a[] = new Integer[n];

for(int i = 0; i < n; i++)

a[i] = con.nextInt();

Integer b[] = new Integer[n];

for(int i = 0; i < n; i++)

b[i] = con.nextInt();

Arrays.sort(a);

Arrays.sort(b);

int res = 0;

for (int i = 0; i < n; i++)

if (Math.abs(a[i] - b[i]) > res) res = Math.abs(a[i] - b[i]);

System.out.println(res);

con.close();

}

}

Python realization

Read the input data.

n = int(input())

a = list(map(int, input().split()))

b = list(map(int, input().split()))

Sort the arrays.

a.sort()

b.sort()

Compute the maximum differences among the absolute values of | b[i] – a[i] |.

res = 0

for i in range(n):

if abs(a[i] - b[i]) > res: res = abs(a[i] - b[i])

Print the answer.

print(res)