Merge Intervals (Function)
PHP
Hard
7 views
Problem Description
Given n intervals, merge overlaps and print the merged intervals sorted by start.
Input Format
First n. Next n lines l r.
Output Format
First line m. Next m lines merged.
Sample Test Case
Input:
4
1 3
2 6
8 10
9 12
Official Solution
<?php
$inputText=rtrim(stream_get_contents(STDIN));
if($inputText==='') exit;
$inputLines=preg_split('/\\R/', $inputText);
$n=intval(trim($inputLines[0] ?? '0'));
$seg=[];
for($i=1;$i<=$n;$i++){
$tokens=preg_split('/\\s+/', trim($inputLines[$i] ?? ''));
$l=intval($tokens[0] ?? 0);
$r=intval($tokens[1] ?? 0);
if($l>$r){ $t=$l; $l=$r; $r=$t; }
$seg[] = [$l,$r];
}
function mergeIntervals($seg){
usort($seg,function($a,$b){
if($a[0]===$b[0]) return $a[1] <=> $b[1];
return $a[0] <=> $b[0];
});
$output=[];
foreach($seg as $it){
if(!$output || $it[0]>$output[count($output)-1][1]) $output[]=$it;
else $output[count($output)-1][1]=max($output[count($output)-1][1],$it[1]);
}
return $output;
}
$res=mergeIntervals($seg);
$output=[strval(count($res))];
foreach($res as $it) $output[]=$it[0].' '.$it[1];
echo implode(PHP_EOL,$output);
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!