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