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:

- Are the pairs sorted?
- Do pairs overlap?
- 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.

The content is written by members of the stackoverflow.com community.

It is licensed under cc-wiki