Max Overlapping Intervals
PHP
Hard
6 views
Problem Description
Given n intervals [l,r], find the maximum number of overlaps at any point.
Input Format
First n. Next n lines: l r.
Output Format
One integer maxOverlap.
Official Solution
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$n=intval(trim($inputLines[0] ?? '0'));
$events=[];
for($i=1;$i<=$n;$i++){
$tokens=preg_split('/\\s+/', trim($inputLines[$i] ?? ''));
$l=intval($tokens[0] ?? 0);
$r=intval($tokens[1] ?? 0);
$events[] = [$l, 1];
$events[] = [$r+1, -1];
}
usort($events,function($a,$b){
if($a[0]===$b[0]) return $a[1] <=> $b[1];
return $a[0] <=> $b[0];
});
$cur=0; $best=0;
foreach($events as $e){
$cur += $e[1];
if($cur>$best) $best=$cur;
}
echo $best;
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!