Создать новый массив на основе массива перекрывающихся сущностей

Question

У вас когда-нибудь был один из тех дней, когда ваш мозг просто не выходил из 1-й передачи?

У меня есть массив, содержащий время начала и окончания. Я хотел бы создать новый массив, показывающий ключи перекрывающихся записей из исходного массива. Итак, скажем, у нас есть некоторые «оговорки». Любые перекрывающиеся «резервирования» принадлежат одной и той же «сессии». Исходный массив, такой как:

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

сгенерирует новый массив, например:

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

Какой самый эффективный способ сделать это для больших массивов? Спасибо!

Answer 1

Для каждого резервирования, поместите его (start, id) и (end, id) (отдельно) в массив кортежей, отсортированных по первому элементу (т.е. по времени). Затем перейдите по массиву от самого низкого времени к самому высокому, сохраняя Резервирование открыто, помещая каждого нового в ту же сессию. Как только последнее резервирование в сеансе закрыто, закройте сеанс.

Answer 2

Не настоящий код и, следовательно, не проверен, но может быть способ:

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

    }
}