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 "
";
print_r($results);
echo "
";