14 September 2014

Quiz 26: Minimum time for all rats to hide

Problem:
There are n rats and n holes in a straight line. Each hole can accommodate only 1 rat. A rat may move to its right or left. To move 1 block, he needs 1 minute. Find minimum time required for all rats to occupy a hole from their current position.

Input Format:
Line1: position of rats separated by space
Line2: position of holes separated by space

Output Format:
minimum time required

Constraints:
none

Sample Input
1 2 7
0 8 9

Sample Output:
6

Explanations:-
Rat and hole initial positions: O R R _ _ _ _ R O O
So rat 1 will move 1 position left, rat 2 will move 6 position right and rat 3 will move 2 position right, so minimum time for all rats to occupy holes is 6

Solution:

chomp($mouse=<STDIN>); @arrm=split(" ",$mouse);
chomp($holes=<STDIN>); @arrh=split(" ",$holes);
@arrh1=sort{$a<=>$b}@arrh;
@min=();
@h=();
@arrm1=sort{$a<=>$b}@arrm;
$c=0; for($m=0;$m<$n;$m++) { if($arrm1[$m] ==$arrh1[$m]) {$c++;
}
}
$diff=0;$n1=$n; @arrm=sort{$a<=>$b}@arrm;$k=0;
foreach(@arrm1)
{
if($c ==$n)
{
push(@min,$diff); }$diff1 = $_ -$arrh1[$k];$k++;
if($diff1<0) {$diff1 = $diff1 * -1; } push(@min,$diff1);
}
@ans=sort{$a<=>$b}@min;
print "$ans[$n-1]";

Tips:
Sort holes and rat positions and max(h(i)-r(i)) is the answer