Question

How to add a new interval into a sorted array of non‑overlapping intervals in PHP

Answer 1

function insertInterval(array $intervals, array $newInterval): array {
    $result = [];
    $i = 0;
    $n = count($intervals);

    // 1. Add all intervals that end BEFORE the new interval starts.
    // These cannot overlap.
    while ($i < $n && $intervals[$i][1] < $newInterval[0]) {
        $result[] = $intervals[$i];
        $i++;
    }

    // 2. Merge all intervals that DO overlap with the new interval.
    // Overlap condition: intervals[i].start <= newInterval.end
    while ($i < $n && $intervals[$i][0] <= $newInterval[1]) {
        $newInterval[0] = min($newInterval[0], $intervals[$i][0]);
        $newInterval[1] = max($newInterval[1], $intervals[$i][1]);
        $i++;
    }

    // Add the merged interval
    $result[] = $newInterval;

    // 3. Add all remaining intervals (those starting AFTER new interval ends)
    while ($i < $n) {
        $result[] = $intervals[$i];
        $i++;
    }

    return $result;
}

// Usage:
$intervals = [
    [1, 3],
    [6, 8],
    [13, 18]
];

$newInterval1 = [9, 11];
$updated = insertInterval($intervals, $newInterval1);

$newInterval2 = [2, 5];
$updated = insertInterval($updated, $newInterval2);

echo "Updated intervals:\n";
foreach ($updated as $iv) {
    echo "[" . $iv[0] . "," . $iv[1] . "] ";
}



/*
run:

Updated intervals:
[1,5] [6,8] [9,11] [13,18]

*/

 

70+ SQL courses for beginners and professionals