public
Last active

Find max overlapping intervals algorithm implementation in PHP. See also: http://stackoverflow.com/a/4542928/181664

  • Download Gist
findMaxOverlappingIntervals.php
PHP
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
<?php
/**
* Find the maximum number of overlapping intervals.
*
* For example, given a series of the following int-based intervals [[1,2], [3,4], [2,10]]
* the following intervals overlap: [1,2] with [2,10], [3,4] with [2,10], hence the maximum
* number of overlapping intervals is 2.
*
* @link http://stackoverflow.com/a/4542928/181664
* @param array $series An array of pairs of positive integers, i.e. [[1,2], [3,4], [2,10] ...]
* @return integer Maximum number of overlapping intervals.
* @throws \BadFunctionCallException
*/
function findMaxOverlappingIntervals($series){
if(!is_array($series)){
throw new \BadFunctionCallException('Expected an array of series, given '.gettype($series));
}
if (!count($series)) {
return 0;
}
 
// Flatten series
$flatSeries = array();
foreach($series as $s){
if(!$s[0] || !$s[1] || $s[0] <= 0 || $s[1] <= 0 || $s[1] < $s[0]){
throw new \BadFunctionCallException(
'The interval ' . $s .' is invalid'
);
}
$flatSeries[] = $s[0]; // start is positive
$flatSeries[] = -$s[1]; // ending is given negative value
}
 
// Sort the flat series by absolute value, ascending
usort($flatSeries, function($a, $b){
return abs($a) - abs($b);
});
 
// Calculate the max overlap (branching) number.
$max = 1;
$counter = 1;
for($x = 0; $x < count($flatSeries); $x++){
if($flatSeries[$x] > 0){
$counter++;
}else{
$counter--;
}
$max = max($max, $counter);
}
return $max;
}
<?php
// Data
$intervals = array(
    array(1, 2),
    array(2, 3),
    array(4, 5),
    array(1, 5),
);

// Heap keeping sorting
class Intervals extends SplHeap
{
    public function compare($value1, $value2)
    {
        $value1 = abs($value1);
        $value2 = abs($value2);

        if ($value1 === $value2) {
            return 0;
        }

        return $value1 < $value2 ? 1 : -1;
    }
}

// Insert intervals
$values = new Intervals();

foreach ($intervals as $interval) {
    $values->insert($interval[0]);
    $values->insert(-$interval[1]);
}

// Track overlapping intervals
$overlaps = 0;
$level    = 0;

foreach ($values as $value) {
    if ($value > 0) {
        if ($level > 0) {
            $overlaps++;
        }

        $level++;
    } else {
        $level--;
    }
}

var_dump($overlaps);

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.