Create a new array based on an array of overlapping entities

Do you ever just have one of those days where your brain just doesn't get out of 1st gear?

I have an array containing start and end times. I'd like to create a new array showing the keys of the overlapping entries from the initial array. So, say we have some 'reservations'. Any overlapping 'reservations' belong to the same 'session'. An initial array 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
            )
    )

would generate a new array like:

[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!

For every reservation, put its (start,id) and (end,id) (separately) into an array of tuples sorted on first item (i.e. time.) Then go over the array from lowest time to highest, keeping what reservations are open, putting every new one in the same session. Once the last reservation in the session is closed, close the session.

Not real code and thus not tested, but could 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

    }
}