pedmillon pedmillon - 4 months ago 13
PHP Question

Removing enclosed intervals in an array of intervals in PHP

I have such an array of intervals sorted by the lower bound ($a[$i] <= $a[$i+1] for every $i), key l is lower bound and , key h is upper bound and I'd like to remove all rows with intervals that are enclosed by larger intervals.

$a[0] = array('l' => 123, 'h'=>241);
$a[1] = array('l' => 250, 'h'=>360);
$a[2] = array('l' => 280, 'h'=>285);
$a[3] = array('l' => 310, 'h'=>310);
$a[4] = array('l' => 390, 'h'=>400);


So the result I'd like to get is

$a[0] = array('l' => 123, 'h'=>241);
$a[1] = array('l' => 250, 'h'=>360);
$a[2] = array('l' => 390, 'h'=>400);


This is what I attempted

function dup($a){
$c = count($a)-1;
for ($i = $c; $i > 0; $i --){
while ($a[$i]['h'] <= $a[$i-1]['h']){
unset($a[$i]);
}
}
$a = array_values($a);
}

Answer

A simplistic approach, maybe not exactly what you want, but should at least point you in the right direction. I can refine it if needed, just a bit busy and didn't want to leave the question unanswered..

$out = [];

foreach ($a as $valA)
{
  $found = false;

  foreach ($a as $valB)
  {
    if (($valA['l'] > $valB['l']) && ($valA['h'] < $valB['h']))
    {
      $found = true;
      break;
    }
  }

  if (!$found)
  {
    $out[] = $valA;
  }
}

This is entirely untested, but should end up with only the unique (large) ranges in $out. Overlaps as I mentioned in my comment are unhandled.