Merge Intervals (Function)

Merge Intervals (Function)

Hard PHP PHP Functions 32 views
Explanation Complexity

Problem Statement

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.

Example

4
1 3
2 6
8 10
9 12
2
1 6
8 12

Constraints

n

Input / Output Format

Input Format
First n. Next n lines l r.
Output Format
First line m. Next m lines merged.
Constraints
n

Examples

Input:
4 1 3 2 6 8 10 9 12
Output:
2 1 6 8 12

Example Solution (Public)

PHP 
<?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);
?>

Official Solution Code

<?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);
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.