Hello! Tell me the algorithm for adding time intervals. That is, we assume an array of intervals:
09:00 - 12:00
13:15 - 14:00
12:00 - 13:00

It is necessary to get the output array like this:
09:00 - 13:00
13:15 - 14:00

That is, if the intervals lie nearby, then they merge into one (in the example, they merge and turn out to be 09:00 - 13:00).
I only got this code:

$array[] = array('start'=>'12:00', 'end'=>'13:00'); $array[] = array('start'=>'09:00', 'end'=>'12:00'); $array[] = array('start'=>'13:15', 'end'=>'14:00'); $newints = array(); foreach($array as $arr) { foreach($newints as $key=>$nint) { if($arr['start']==$nint['end']) { $newints[$key]['end'] = $arr['end']; echo 'test'; continue 2; } if($arr['end']==$nint['start']) { $newints[$key]['start'] = $arr['start']; continue 2; } } $newint['start'] = $arr['start']; $newint['end'] = $arr['end']; $newints[] = $newint; } var_dump($newints);

It seems to work correctly, but in my opinion, the code could be more elegant, and therefore some nuances are probably concealed due to which there may be bugs. Please, help)

  • and if the intervals overlap? for example 09: 00-11: 00 and 10: 00-11: 30 - rjhdby
  • There will be problems if the intervals can come to the end of the day - for example, 23:00 - 1:00. - Goncharov Alexander
  • By the way there is a solution for N log N and here is a square. And yes, at the expense of intersections, the correct remark. - pavel
  • But if you first translate all the intervals in the number of minutes from 00:00, it will be much easier. Or even in unix_time, if the full date is known - rjhdby
  • Yes, I did not take into account these nuances. But the intervals are all within the same day go at my base and the intersection is impossible, since this is the time of recording to the person. Of course, it would be nice if someone suggested the most universal algorithm - iproger

2 answers 2

Make closures to increase readability and make the algorithm universal:

 $intervals[] = array('start'=>'12:00', 'end'=>'13:00'); $intervals[] = array('start'=>'09:00', 'end'=>'12:00'); $intervals[] = array('start'=>'13:15', 'end'=>'14:00'); $intervalsMerged = []; foreach($intervals as $interval) { if (!empty($intervals[$key]['already_merged'])) continue; if ($intersects = $anotherIntervalsInersectsWith($interval)){ $intervalsMerged[] = $mergeIntervals($intersects); //тонкий момент - если интервалы уже слиты, ещё раз их учитывать не нужно foreach(array_keys($intersects) as $key){ $intervals[$key]['already_merged'] = 1; } }else{ $intervalsMerged[] = $interval; } }

I suggest to implement closures independently:

$anotherIntervalsInersectsWith - recursively checks with which intervals the given intersects. Recursively, since the addition of an interval to the checked one requires verification again - because borders have changed. Returns an array with the correct $ intervals source array keys — a subset of $ intervals.

$mergeIntervals - merges several into one: just search for the minimum and maximum, but which is slightly complicated by the transition of the day 24:00 -> 00:00. Returns a string.

And do not call the variable $ array, preferably never :)

  • Thanks, just how do you determine if the gaps intersect? $ anotherIntervalsInersects With how it is implemented, at least purely condition - iproger
  • @iproger is a cycle at $ intervals where it checks that start2 <end1 && end2> start1 || start1 <end2 && end1> start2 (I could be wrong - it’s better to draw intervals on paper - it’s straightforward). Time is converted to a numerical value for comparison - as rjhdby wrote. - Goncharov Alexander
  • Thank you very much! I will do! - iproger

If the initial array is constructed by truncating the full date, then we skip this step and form an array in which the keys are unix_timestamp from start, and values ​​unix_timestamp from end. Then we sort by key and in one pass of the array we do all the work.

If the initial data is exactly the time type HH: mm, then about the same, but the keys / values ​​are generated as HH * 60 + mm

  • Wow, thank you, come up with cool !! I hope I understand you now I will try to write the code - iproger