# Calculations of ranges of numbers in PHP

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?

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.