php - Fill gaps in a time schedule

A daily schedule starts at 08:30 and ends at 17:00 (time represented via a begin 'nn:nn' string and end 'nn:nn' string).

Time blocks can only begin and end on :00, :15, :30, :45 of the hour.

A given schedule will have zero or more (non-overlapping) blocks of time pre-booked (of variable block size--anything from one block of 8:30-17:00; or could be many small blocks of 15-minute, half hour, multi-hour blocks, etc).

Example Input:

$schedule = [
    [
        'begin' => '10:00',
        'end' => '12:30'
    ],
    [
        'begin' => '15:15',
        'end' => '16:00'
    ]
];
Copy code

Example Output:

$gapFiller =
[
    [
        'begin' => '08:30',
        'end' => '10:00'
    ],
    [
        'begin' => '12:30',
        'end' => '15:15'
    ],
    [
        'begin' => '16:00',
        'end' => '17:00'
    ]
];
Copy code

Create a function that returns an array of zero or more blocks to fill all the gaps present in an pre-booked schedule. Make block spans as large as possible without overlapping any other blocks.

function fillGaps($schedule){
    //code...

    return $gapFiller;
}

$gapFiller = fillGaps($schedule);
Copy code