and first of all, thank you for taking the time to read my question.

I am trying to write a script, and I've come across an issue which I am finding hard to solve. I am working with a pair of numbers (for example, 1000 and 2000), and I have an array of pairs of numbers:

$pairs = array(
    array(800, 1100),
    array(1500, 1600),
    array(1900, 2100)
)

What I am trying to find, is how to get the ranges not covered by the number pairs, between 1000 and 2000. In this example, 1000-1100 is covered by array(800, 1100), 1500-1600 is covered by array(1500, 1600) and 1900-2000 is covered by array(1900, 2100), which leaves me with 1101-1499 and 1599-1899 left to cover. I hope I am being clear enough.

What I am wondering is how I would make PHP return to me an array of the ranges not covered by the $pairs variable. In this example it would return:

array(
    array(1101, 1499),
    array(1599, 1899)
)

Do you have any idea what would be the best way to do this?

Thank you in advance.

Accepted Answer

Well, firstly you have to define the problem:

  1. Are the pairs sorted?
  2. Do pairs overlap?
  3. You want to find the missing ranges for a particular range (this seems to be the case)?

If pairs aren't sorted, first sort them:

usort($pairs, 'cmp_pair');

function cmp_pair($a, $b) {
  if ($a[0] == $b[0]) {
    if ($a[1] == $b[1]) {
      return 0;
    } else {
      return $a[1] < $b[1] ? -1 : 1;
    }
  } else {
    return $a[0] < $b[0] ? -1 : 1;
  }
}

If overlapping ranges are allowed, transform the list of pairs to a non-overlapping set. Here's one suggestion on how to do that:

$prev = false;
$newpairs = array();
foreach ($pairs as $pair) {
  if ($prev) {
    // this also handles the case of merging two ranges
    // eg 100-199 with 200 to 250 to 100-250
    if ($prev[1] >= $pair[0]-1) {
      $prev = array($prev[0], max($prev[1], $pair[1]));
    } else {
      $newpairs[] = $prev;
    }
  }
  $prev = $pair;
}
$pairs = $newpairs;

Now there shouldn't be any overlapping pairs so the problem becomes a little simpler as you've also got a sorted array.

function missing($start, $end, $pairs) {
  $missing = array();
  $prev = false;
  foreach ($pairs as $pair) {
    // if the current pair starts above the end, we're done
    if ($pair[0] > $end) {
      break;
    }

    // we can ignore any pairs that end before the start
    if ($pair[1] < $start) {
      continue;
    }

    // if the pair encompasses the whole range, nothing is missing
    if ($pair[0] <= $start && $pair[1] >= $end) {
      break;
    }

    // if this is our first overlapping pair and it starts above
    // the start we can backfill the missing range
    if ($pair[0] > $start && !$missing) {
      $missing[] = array($start, $pair[0]);
    }

    // compare this pair to the previous one (if there is one) and
    // fill in the missing range
    if ($prev) {
      $missing[] = array($prev[1]+1, $pair[0]-1);
    }

    // set the previous
    $prev = $pair;
  }

  // if this never got set the whole range is missing
  if (!$prev) {
    $missing[] = array($start, $end);

  // if the last overlapping range ended before the end then
  // we are missing a range from the end of it to the end of
  // of the relevant range
  } else if ($prev[1] < $end) {
    $missing[] = array($prev[1]+1, $end);
  }

  // done!
  return $missing;
}

Hope that helps.

Written by cletus
This page was build to provide you fast access to the question and the direct accepted answer.
The content is written by members of the stackoverflow.com community.
It is licensed under cc-wiki