smallest-range.php

<?php

$list = [[1,  2, 3, 9, 20],
    [4, 10, 12, 21, 40],
    [5, 11, 13, 22],
    [6, 8, 10, 23, 24, 25, 26]];


abstract class MyHeap
{
    private $heap = array();

    public function insert($item)
    {
        // smallest item is first
        for ($i = 0; $i < count($this->heap); ++$i) {
            if ($this->compare($item, $this->heap[$i]) <= 0) {
                if ($i == 0) {
                    array_unshift($this->heap, $item);
                } else {
                    array_splice($this->heap, $i, 0, array($item));
                }
                return $item;
            }
        }
        return array_push($this->heap, $item);
    }

    public function top()
    {
        return $this->heap[0];
    }

    public function bottom()
    {
        return $this->heap[count($this->heap) - 1];
    }

    public function extract()
    {
        return array_shift($this->heap);
    }

    public function isEmpty()
    {
        return count($this->heap) === 0;
    }

    abstract function compare($a, $b);
}

class RangeHeap extends MyHeap
{
    public function compare($a, $b)
    {
        return $a['value'] - $b['value'];
    }
}

function range_start($list)
{
    $range = new RangeHeap;

    foreach ($list as $key => $item) {
        $range->insert(array(
            'value' => $item[0],
            'list' => $key,
            'index' => 0,
        ));
    }

    return $range;
}

function range_expand(RangeHeap $range, array $list)
{
    while (!$range->isEmpty()) {
        $item = $range->extract();
        if ($item['index'] + 1 < count($list[$item['list']])) {
            $item['value'] = $list[$item['list']][++$item['index']];
            $range->insert($item);
            return true;
        }
    }

    return false;
}

function range_size($range)
{
    // calculate range size
    $first = $range->top();
    $last = $range->bottom();

    return array($first['value'], $last['value'], $last['value'] - $first['value']);
}

$range = range_start($list);
$min_size = null;

do {
    list($first, $last, $size) = range_size($range);
    if ($min_size === null || $size < $min_size[2]) {
        $min_size = array($first, $last, $size);;
    }
} while (range_expand($range, $list));

print_r($min_size);