Create a new array based on an array of overlapping objects

Question

Have you ever had one of those days when your brain just didn’t leave the first gear?

I have an array containing the start and end time. I would like to create a new array showing the keys of the overlapping entries from the original array. So, let's say we have some “reservations”. Any overlapping “reservations” refer to the same “session”. The initial array is like:

[reservations] => Array ( [1125] => Array ( [start] => 2011-01-07 10:00:00 [end] => 2011-01-07 10:30:00 ) [1244] => Array ( [start] => 2011-01-07 10:15:00 [end] => 2011-01-07 11:30:00 ) [1311] => Array ( [start] => 2011-01-07 11:00:00 [end] => 2011-01-07 11:45:00 ) [1422] => Array ( [start] => 2011-01-07 12:00:00 [end] => 2011-01-07 12:30:00 ) [1561] => Array ( [start] => 2011-01-07 12:30:00 [end] => 2011-01-07 12:45:00 ) [1622] => Array ( [start] => 2011-01-07 13:00:00 [end] => 2011-01-07 13:45:00 ) ) 

will create a new array, for example:

 [sessions] => Array ( [0] => Array ( [0] => 1125 [1] => 1244 [2] => 1311 ) [1] => Array ( [0] => 1422 [1] => 1561 ) [2] => Array ( [0] => 1622 ) ) 

What would be the most efficient way to do this for large arrays? Thanks!

Answer 1

For each reservation, put it (start, id) and (end, id) (separately) in an array of tuples sorted by the first element (i.e. time). Then, go through the array from the minimum time to the highest, keeping the reservations open, each new in one session. After closing the last reservation in the session, close the session.

Answer 2

Not real code and therefore not verified, but there may be a way:

 foreach([reservations] as $key => $res){ $a[ timestamp_of( $res[start] ) ] = $key; $a[ timestamp_of( $res[end] ) ] = $key; } ksort($a, SORT_NUMERIC); //sort by timestamp $open = Array(); //currently 'open' reservations while looping through $sesions = Array(); //result array for sessions $active = 0; //ID of active session foreach($a as $item){ if($item in $open) { //check if current reservation is in list of open ones strip($item, $open); //if so: close it → remove from array if( sizeof( $open ) == 0 ) $active++; //if no reservations open, close the session } else { //if current reservation is not open... $open[$item] = true; //open it $sessions[$active][] = $item //and add it to current session } }