Stack Overflow Q# 11965455

<?php

class LineSegment {
    public $user_id;
    public $start_point;
    public $end_point;

    public function __construct($user_id, $start_value, $end_value) {
        $this->user_id = $user_id;
        $this->start_point = new Endpoint($start_value, $user_id, TRUE);
        $this->end_point = new Endpoint($end_value, $user_id, FALSE);
    }

    public function __toString() {
        return "$user_id [{$start_point->value}, {$end_point->value}]";
    }
}

class Endpoint {
    public $value;
    public $user_id;
    public $is_start;

    public function __construct($value, $user_id, $is_start) {
        $this->value = $value;
        $this->user_id = $user_id;
        $this->is_start = $is_start;
    }

    public function __toString() {
        $location = $this->is_start ? "start" : "end";
        return "{$this->user_id}: {$this->value} ($location)";
    }
}

class ResultSegment {
    public $user_ids;
    public $start_value;
    public $end_value;

    public $num_users;
    public $duration;

    public function __construct($user_ids, $start_value, $end_value) {
        $this->user_ids = $user_ids;
        $this->start_value = $start_value;
        $this->end_value = $end_value;
        $this->num_users = count($user_ids);
        $this->duration = $end_value - $start_value; //assumption: values are numeric (insert your own function here)
    }
}

class Sweepline {
    public $last_endpoint_value; //value of last encountered endpoint
    public $last_endpoint_was_end; //last encountered endpoint was an end (right) endpoint
    public $active_users; //set of user IDs (user_id => user_id)
    public $result_segments; //value-sorted array of LineSegments (with user_id being the number of available users)

    public function __construct() {
        $this->last_endpoint_value = 0;
        $this->last_endpoint_was_end = false;
        $this->active_users = array();
    }

    public function execute($endpoints) {
        $this->result_segments = array();
        foreach ($endpoints as $endpoint) {
            $this->advance($endpoint);
        }
        return $this->result_segments;
    }

    public function advance(Endpoint $next_endpoint) {
        $user_id = $next_endpoint->user_id;
        if ($next_endpoint->is_start) {
            $this->active_users[$user_id] = $user_id;
        } else {
            //when multiple segments end at the same value, you only need one result
            if (!$this->last_endpoint_was_end) {
                $result = new ResultSegment(array_values($this->active_users), $this->last_endpoint_value, $next_endpoint->value);
                $this->result_segments[] = $result;
            }
            unset($this->active_users[$user_id]);
        }
        $this->last_endpoint_was_end = !$next_endpoint->is_start;
        $this->last_endpoint_value = $next_endpoint->value;
    }
}


function endpoint_comparer(Endpoint &$point1, Endpoint &$point2) {
    if ($point1->value == $point2->value) {
        if ($point1->is_start != $point2->is_start) {
            return $point1->is_start ? -1 : 1; //ending points before starting
        }
    }
    return $point1->value > $point2->value;
}

function result_comparer(ResultSegment &$line1, ResultSegment &$line2) {
    if ($line1->num_users == $line2->num_users) {
        return $line1->duration > $line2->duration;
    }
    return $line1->num_users > $line2->num_users;
}


//1) Create line-segments (assumption: for each line-segment, start_value is less than end_value)
$segments = array(
        new LineSegment(1, 10, 20),
        new LineSegment(1, 40, 74),
        new LineSegment(2, 19, 25),
        new LineSegment(2, 34, 50),
        new LineSegment(3, 15, 25),
        new LineSegment(3, 55, 90),
    );

//1a) TODO: merge same-user segments that start/end at the same time.

//2) create a sorted array of all endpoints (start and end)
$endpoints = array();
foreach ($segments as $segment) {
    $endpoints[] = $segment->start_point;
    $endpoints[] = $segment->end_point;
}
usort($endpoints, 'endpoint_comparer');

//3) Initialize sweep-line
$sweepline = new Sweepline();

//4) Execute sweep-line
$results = $sweepline->execute($endpoints);

//5) Sort results
usort($results, 'result_comparer');
$results = array_reverse($results);


echo "<pre>";
print_r($results);
echo "</pre>";