2
$\begingroup$

Problem

Given a set of intervals with possibly non-distinct start and end points, find all maximal gaps. A gap is defined as an interval that does not overlap with any given interval. All endpoints are integers and inclusive.

For example, given the following set of intervals:

$\{[2,6], [1,9], [12,19]\}$

The set of all maximal gaps is:

$\{[10,11]\}$

For the following set of intervals:

$\{[2,6], [1,9], [3,12], [18,20]\}$

The set of all maximal gaps is:

$\{[13,17]\}$

because that produces the maximal gap.

Proposed Algorithm

My proposed algorithm (modified approach taken by John L.) to compute these gaps is:

  1. Order the intervals by ascending start date.
  2. Initialise an empty list gaps that will store gaps
  3. Initialise a variable, last_covered_point, to the end point of the first interval.
  4. Iterate through all intervals in the sorted order. For each interval [start, end], do the following.
    1. If start > last_covered_point + 1, add the gap, [last_covered_point + 1, start - 1] to gaps.
    2. Assign max(last_covered_point, end) to last_covered_point.
  5. Return gaps

I have tested my algorithm on a few cases and it produces the correct results. But I cannot say with 100% guarantee that it works for every interval permutation and combination. Is there a way to prove this handles every permutation and combination?

$\endgroup$
1
  • $\begingroup$ @JohnL. yes the question is correct now - thanks $\endgroup$
    – Mojo
    Dec 18 '20 at 21:25
4
$\begingroup$

The key to prove your algorithm is correct is to find enough invariants of the loop, step 4 so that we apply use mathematical induction.


Let $I_1, I_2, \cdots, I_n$ denote the sorted intervals. When the algorithm has just finished processing $I_i$, we record the values of gaps and last_covered_point as $\text{gaps}_i$ and $\text{last_covered_point}_i$ respectively.

Let us prove the following proposition, $P(i)$, for $i=1, 2, \cdots, n$.

$\text{gaps}_i$ is the set of all maximal gaps for $I_1, I_2, \cdots, I_i$ and $\text{last_covered_point}_i$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_i$.

When $i=1$, $\text{gaps}_1$ is the empty set and $\text{last_covered_point}_1$ is the right endpoint of $I_1$. So $P(1)$ is correct.

For the sake of mathematical induction, assume $P(i)$ is correct, where $1\le i\lt n$. Let $I_{i+1}=[s, e]$. There are two cases.

  1. If $s\gt\text{last_covered_point}_i+1$, then $$\text{gaps}_i\cup[\text{last_covered_point}_i +1, s-1]=\text{gaps}_{i+1}.$$
    Let $m$ be any point between the start point of $I_1$ and the maximum of all right endpoints of $I_1, I_2, \cdots, I_{i+1}$. Suppose $m$ not covered by any of $I_1, I_2, \cdots, I_{i+1}$.

    • If $m\le\text{last_covered_point}_i$, the induction hypothesis says that $m$ is covered by some interval in $\text{gap}_i$.
    • Otherwise, $m\gt\text{last_covered_point}_i$. Since $m$ is not covered by $I_{i+1}$, we know $m<s$. So $m$ is covered by $[\text{last_covered_point}_i +1, s-1]$.

    In both cases, $m$ is covered by some interval in $\text{gaps}_{i+1}$. Since $\text{last_covered_point}_i$ is the largest point covered by one of $I_1, I_2, \cdots, I_i$ and $s$ is the smallest point covered by $I_{i+1}$, $[\text{last_covered_point}_i +1, s-1]$ is a maximal gap.

  2. Otherwise, we have $s\le\text{last_covered_point}_i$+1. We can also verify that $\text{gaps}_{i+1}=\text{gaps}_{i}$ is the set of all maximal gaps for $I_1, I_2, \cdots, I_{i+1}$.

Finally, since step 4.2 says $\text{last_covered_point}_{i+1}=\max(\text{last_covered_point}_i, e)$ and $\text{last_covered_point}_i$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_i$, $\text{last_covered_point}_{i+1}$ is the maximum of all right endpoints of $I_1, I_2, \cdots, I_{i+1}$.

So, $P(i+1)$ is correct. $\quad\checkmark$.

$\endgroup$
4
  • $\begingroup$ I probably didn't make my post precise enough and so I think you may have misunderstood what I meant by a gap. I have cleaned up my original post to define the problem better but I also took your example and customised it to what I think the algorithm should be. The main issue I have is that I am not sure if I have covered all possible interval permutations. $\endgroup$
    – Mojo
    Dec 17 '20 at 15:19
  • $\begingroup$ @Mojo, thanks for noticing that last_covered_point should be updated in step 4.2 as well. $\endgroup$
    – John L.
    Dec 18 '20 at 16:30
  • $\begingroup$ @Mojo, I just wrote a proof. The proof is not completely formal, since "maximal gap" is given by a definition (although it is easy to define) and the case 2 is not proved in detail. However, the idea should be clear enough. $\endgroup$
    – John L.
    Dec 20 '20 at 5:24
  • $\begingroup$ In my last comment, 'since "maximal gap" is given by a definition' should have been 'since "maximal gap" is not given by a definition'. $\endgroup$
    – John L.
    Jan 4 at 1:35
1
$\begingroup$

I'd like to propose a quite simple algorithm as well. The idea is this: we're going to place open and close parentheses on the number line at the boundaries of each interval. For example, for the intervals $(1,5), (2,7), (9, 10)$, the number line would look like this:

1 2 3 4 5 6 7 8 9 10
( (     )   )   ( )

Then we'll just scan left to right, counting parentheses. When all the parentheses get closed, we start a gap. Note in particular that in the above diagram, we have lost the information about which close parenthesis is paired with which open parenthesis -- because it doesn't actually matter. So:

  1. Convert each interval $(a,b)$ to pairs $(a,\mathtt o),(b,\mathtt c)$. ($\mathtt o$ and $\mathtt c$ are for open and close, respectively.)
  2. Sort all the pairs you get from this process. (When sorting, use lexicographic ordering and $\mathtt o < \mathtt c$.)
  3. Iterate through them, keeping a counter that starts from $0$.
    • When you see a pair with $\mathtt o$ in the second part, increment the counter.
    • When you see a pair with $\mathtt c$ in the second part, decrement the counter.
    • When you decrement the counter, if that causes it to drop to $0$, then look at the next element of the list to decide what to do; empty list means you're done, otherwise if the next pair's first part is just one bigger than the current one's you do nothing, and in the last case you record a maximal gap between the current end point and the next open point.
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.