Skip to content

Instantly share code, notes, and snippets.

@saleemkce
Last active January 2, 2016 09:29
Show Gist options
  • Save saleemkce/8283619 to your computer and use it in GitHub Desktop.
Save saleemkce/8283619 to your computer and use it in GitHub Desktop.
Given M busy-time slots of N people, You need to print all the available time slots when all the N people can schedule a meeting for a duration of K minutes.Event time will be of form HH MM ( where 0 <= HH <= 23 and 0 <= MM <= 59 ), K will be in the form minutes.
<?php
/*
Given M busy-time slots of N people, You need to print all the available time slots when all the N people can schedule a meeting for a duration of K minutes.
Event time will be of form HH MM ( where 0 <= HH <= 23 and 0 <= MM <= 59 ), K will be in the form minutes.
Input Format:
M K [ M number of busy time slots , K is the duration in minutes ]
Followed by M lines with 4 numbers on each line.
Each line will be of form StartHH StartMM EndHH EndMM [ Example 9Am-11Am time slot will be given as 9 00 11 00 ]
An event time slot is of form [Start Time, End Time ) . Which means it inclusive at start time but doesn’t include the end time.
So an event of form 10 00 11 00 => implies that the meeting start at 10:00 and ends at 11:00, so another meeting can start at 11:00.
Sample Input:
5 120
16 00 17 00
10 30 14 30
20 45 22 15
10 00 13 15
09 00 11 00
Sample Output:
00 00 09 00
17 00 20 45
*/
$stdin = fopen('php://stdin', 'r');
$input = trim(fgets(STDIN));
$inpData = explode(" ", $input);
$inArray = array();
$uk = 0;
foreach($inpData as $ii)
{
$inputVal = (int)$ii;
if(is_integer($inputVal))
{
$inArray[$uk] = $inputVal;
++$uk;
}
else
{
die("Wrong input format!");
}
}
if($uk < 2 || $uk > 2)
{
die("No of input on first line is wrong!");
}
if(($inArray[0] < 1) || ($inArray[0] > 100) || !preg_match("/^[0-9]+$/",$inArray[0]))
{
die("M should be between 1 and 100");
}
if(empty($inArray[1]) || ($inArray[1] < 1) || ($inArray[1] > 1440) || !preg_match("/^[0-9]+$/", $inArray[1]))
{
die("Wrong total time format in minutes, should be between 1 and 1440!");
}
/*else if($inArray[1] > 1440)
{
die("Duration exceeds day limit, should be less than 1440 preferable!");
}*/
for($i = 0; $i < 4; $i++)
{
global ${"a".$i};
${"a".$i} = array();
${"temp".$i} = array();
}
for($ba = 0; $ba < $inArray[0]; $ba++)
{
$in = trim(fgets(STDIN));
if(empty($in))
{
die("Wrong input format!");
}
$data = explode(" ", $in);
$co = 0;
foreach($data as $dd)
{
if(!preg_match("/^[0-9]+$/",$dd)){
die("Input contains characters, try again!");
}
if($co == 0 || $co == 2)
{
if($dd > 23 || $dd < 0)
{
die("Hour format should be between 0 and 23!");
}
}
if($co == 1 || $co == 3)
{
if($dd > 59 || $dd < 0)
{
die("Minute format should be between 0 and 59!");
}
}
$vals = (int)$dd;
${"temp".$ba}[$co] = $vals;
if($co == 2)
{
if(${"temp".$ba}[$co] < ${"temp".$ba}[0])
{
die("problem with input data in HOUR format!");
}
}
if($co == 3)
{
if((${"temp".$ba}[0]) >= (${"temp".$ba}[2]))
{
if((${"temp".$ba}[1]) > (${"temp".$ba}[3]))
{
die("Minute format contradicts with each other!");
}
}
}
++$co;
}
if($co < 4 || $co > 4)
{
die("Wrong time format!");
}
}
for($ba = 0; $ba < $co; $ba++)
{
for($aa = 0; $aa < $inArray[0]; $aa++)
{
${"a".$ba}[$aa] = ${"temp".$aa}[$ba];
}
}
$a = 0; $b = 1; $c = 2; $d = 3;
$required = $inArray[1];
$total = count(${"a".$a});
$tSa = array(); $tSb = array(); $tEa = array(); $tEb = array();
for($ux = 0; $ux < $total; $ux++)
{
$tSa[$ux] = ${"a".$a}[$ux];
$tSb[$ux] = ${"a".$b}[$ux];
$tEa[$ux] = ${"a".$c}[$ux];
$tEb[$ux] = ${"a".$d}[$ux];
}
$fullArray = array();
$tied = 0; $hour = 24; $min = 60;
for($st = 0; $st < $hour; $st++)
{
for($ne = 0; $ne < $min; $ne++)
{
$fullArray[$st][$ne] = "A";
}
}
for($vl = 0; $vl < $total; $vl++)
{
for($st = 0; $st < $hour; $st++)
{
for($ne = 0; $ne < $min; $ne++)
{
if($tied == 1)
{
$fullArray[$st][$ne] = "u";
}
else if($st == $tSa[$vl] && $ne == $tSb[$vl])
{
$tied = 1;
$fullArray[$st][$ne] = "Us";
}
if($st == $tEa[$vl] && $ne == $tEb[$vl])
{
$fullArray[$st][$ne] = "Ue";
$tied = 0;
}
}
}
}
$start = array(); $end = array(); $tempSt = array(); $result = array();
$counter = 0;
for($st = 0; $st < $hour; $st++)
{
for($ne = 0; $ne < $min; $ne++)
{
if($fullArray[$st][$ne] == "A")
{
++$counter;
if($st != 0)
{
$test = $ne - 1;
}
else
{
$test = $ne;
}
$tempSt[] = $st." ".$test;
$tempSt[] = $st." ".$ne;
}
else if($fullArray[$st][$ne] == "u" || $fullArray[$st][$ne] == "Us" || $fullArray[$st][$ne] == "Ue")
{
if($counter > 0)
{
$tempSt[] = $st." ".$ne;
if($counter >= $required)
{
$tota = count($tempSt);
$result[] = $tempSt[0];
$result[] = $tempSt[$tota-1];
$startT = explode(" ", $tempSt[0]);
$endT = explode(" ", $tempSt[$tota-1]);
$teCount = 0;
$tie = array();
foreach($startT as $hu){
$ress = (int)$hu;
if(strlen($ress) == 1)
{
echo 0;echo $ress; echo " ";//echo "This causes 1";
}
else
{
echo $ress; echo " "; //echo "This causes 2";
}
++$teCount;
}
foreach($endT as $ru){
$ress = (int)$ru;
if(strlen($ress) == 1)
{
echo 0;echo $ress; echo " "; //echo "This causes 3";
}
else
{
echo $ress; echo " "; //echo "This causes 4";
}
}
echo "".PHP_EOL; //echo "This causes 5";
}
$tempSt = array();
}
$counter = 0;
}
}
}
//------------------------------ LAST
$counter = 0; $tempSt = array();
for($st = ($hour - 1); $st >= 0; $st--)
{
for($ne = ($min - 1); $ne >= 0; $ne--)
{
if($fullArray[$st][$ne] == "A")
{
++$counter;
$tempSt[] = $st." ".$ne;
}
else if($fullArray[$st][$ne] == "u" || $fullArray[$st][$ne] == "Us" || $fullArray[$st][$ne] == "Ue")
{
if($counter > 0)
{
$tempSt[] = $st." ".$ne;
if($counter >= $required)
{
$tota = count($tempSt);
$result[] = $tempSt[$tota-1];
$result[] = $tempSt[0];
$startT = explode(" ", $tempSt[0]);
$endT = explode(" ", $tempSt[$tota-1]);
foreach($endT as $ru){
$ress = (int)$ru;
if(strlen($ress) == 1)
{
echo 0;echo $ress; echo " ";//echo "This causes 6";
}
else
{
echo $ress; echo " ";//echo "This causes 7";
}
}
foreach($startT as $hu){
$ress = (int)$hu;
if(strlen($ress) == 1)
{
echo 0;echo 0; echo " "; //echo "This causes 8";
}
else
{
echo 0;echo 0; echo " "; //echo "This causes 9";
}
}
}
$tempSt = array();
}
$counter = 0;
exit;
}
}
}
?>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment