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

findMaxOverlappingIntervals.php

<?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);