подсчет часов с перекрытием времени

Question

У меня различное время, как диапазоны, как

10:00 12:00, 
21:00 24:00, 
11:30 12:00, 
08:00 17:00 

Эти графики пользователя. Я хочу рассчитать общее количество часов с этих диапазонов, но я не хочу вычислять повторяющееся время. Если я вычислил любой час один раз, то я не хочу снова это вычислять. Что я должен сделать для этого.

Я вычисляю часы этим. но как я мог избежать повторного времени. которые я уже посчитал.

$shifts = "10:00 12:00 | 21:00 24:00| 11:30 12:00|08:00 17:00"; 
$shifts = explode('|', $shifts); 

$sum = 0; 

$starts = array(); 
$ends = array(); 

foreach($shifts as $shift) { 
    $times = explode(' ', trim($shift)); 
    $start = explode(':', $times[0]); 
    $end = explode(':', $times[1]); 

    $startime = $start[0]*60 + $start[1]; 
    $endtime = $end[0]*60 + $end[1]; 
    $flag = false; 
    foreach ($starts as $key=>$start) {  
     if($startime < $start && $endtime > $ends[$key]) { 
      $diff_old = ($start > $ends[$key]) ? $start - $ends[$key] : $ends[$key] - $start; 
      $sum = $sum - $diff_old/60; 
     } 
     else if($startime > $start && $endtime <= $ends[$key]) { 
      $flag = true; 
      continue; 
     } 
    } 
    if($flag) 
     continue; 
    $starts[] = $startime; 
    $ends[] = $endtime; 
    $diff = $startime > $endtime ? $startime - $endtime : $endtime - $startime; 
    $sum = $sum + $diff/60; 
} 

echo $sum; 

Я пытаюсь использовать этот код выше, но отображается неправильный ответ. потому что я не хочу вычислять часы, которые уже рассчитаны. на этот раз это ответ 12, но правильный ответ - 10.

Answer 1

Давайте рассмотрим следующее. Если у нас есть два интервала [8, 10] и [9, 12], тогда длина объединения интервалов равна длине [8, 12].

Если у нас есть два непересекающихся интервала ([8, 9] и [10, 11]), нам не нужно делать это слияние интервалов для вычисления длины. Вместо этого мы можем просто взять сумму длин интервалов.

Поэтому логично попытаться уменьшить набор интервалов до набора непересекающихся интервалов. Тогда проблема становится тривиальной.

//Check if [a0, a1] and [b0, b1] are disjoint 
function isDisjoint($a, $b) { 
    if(in_array($a[0], $b) || in_array($a[1], $b)) { 
     return false; 
    } 
    return ($a[0] < $b[0]) ? ($a[1] < $b[0]) : ($a[0] > $b[1]); 
} 

//Make sure $a and $b are not disjoint before calling. 
function mergeIntervals($a, $b) { 
    return array(min($a[0], $b[0]), max($a[1], $b[1])); 
} 

//Generate a set of disjoint intervals 
function genetrateDisjointSet($set) { 
    $output = array(); 
    while(!empty($set)) { 
     $interval = array_pop($set); 
     $intervalDisjoint = false; 

     while(!$intervalDisjoint) { 
     $intervalDisjoint = true; 
     foreach($set as $key => $value) { 
      if(!isDisjoint($interval, $value)) { 
       $interval = mergeIntervals($interval, $value); 
       unset($set[$key]); 
       $intervalDisjoint = false; 
      } 
     } 
    } 

    array_push($output, $interval); 
    } 

    return $output; 
} 

//Calculate the length of the set of intervals 
function calcLength($set) { 
    $set = genetrateDisjointSet($set); 
    $length = 0; 

    foreach($set as $value) { 
     $length += $value[1] - $value[0]; 
    } 

    return $length; 
} 

Мы пытаемся это с вашим примером

//You have to convert the time to minutes after 00:00. 
$set = array(
    array(600, 720), 
    array(1260, 1440), 
    array(690, 720), 
    array(480, 1020) 
); 
echo calcLength($set); //720 min = 12 h * 60 

Примечание что 08:00 к 17:00 + 21:00 к 24:00 является 9 + 3 = 12

Редактировать Изменено время до нескольких минут после того, как 00:00 вместо часов , Спасибо Дхарману за эту идею.