intervals.php

<?php
/*
 * Problem:
 * Given a set of intervals, print all NON overlapping intervals
 * after merging overlapping intervals.
 *
 * Assumptions:
 * 1. The start of the interval is less than or equal to the end
 * 2. The input is sorted by the start of the interval in asc order
 * 3. The intervals are made u of positive integers
 */

// The sample input from the problem
$input = [
    [1, 5],
    [2, 3],
    [4, 6],
    [7, 8],
    [8, 10],
    [12, 15],
];

/*
 * Expected output:
 * $input = [
 *   [1, 6],
 *   [7, 10],
 *   [12, 15],
 * ];
 */

// Sort by the start of the interval
usort($input, function ($a, $b) {
    return $a[0] - $b[0];
});

$output = [];

// While we still have unchecked intervals
while (count($input)) {
    // Get and remove the first interval from the input
    $current = array_shift($input);

    // Iterate through the the remaining ordered intervals
    // and merge overlapping intervals until
    // we exceed the upper bounds of the current merged interval
    foreach ($input as $index => $interval) {
        // Break if no overlap is possible
        if ($current[1] < $interval[0]) {
            break;
        }

        // Must have overlap based on sorting so
        // increase the end of the current if necessary
        $current[1] = $current[1] > $interval[1]
            ? $current[1]
            : $interval[1];

        // Remove merged interval from the input
        unset($input[$index]);
    }

    // Add fully merged interval to output list
    $output[] = $current;
}

print_r($output);