0
$\begingroup$

I want to verify the correctness of this algorithm.

Problem: given a list of intervals, where the first index is greater than the second, determine if every interval overlaps with every other interval.

Examples

----
  ----
True


--------
  --
  -
True


----
    ---
False


-----
 ---
-
False, 3rd line does not overlap with second

This Typescript solution finds the maximum start and minimum end of all intervals. Then it checks that every interval overlaps the max start and min end.

const overlaps = ([min1, max1]: [number, number], [min2, max2]: [number, number]): boolean => {
    const overlapDist = Math.max(0, Math.min(max1, max2) - Math.max(min1, min2))
    return overlapDist > 0
} 

export const allOverlap = (intervals: [number, number][]): boolean => {
    const [maxStart, minEnd] = intervals.reduce(([maxStart, minEnd], [start, end]) => {
        const ms = (start > maxStart) ? start : maxStart
        const me = (end < minEnd) ? end : minEnd
        return [ms, me]

    }, [-Infinity, Infinity])

    if (minEnd < maxStart)
        return false

    for (const interval of intervals) {
        if (!overlaps([maxStart, minEnd], interval))
            return false
    }

    return true
}

From my tests, this seems to work. However, I am unsure how to prove its correctness.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

Let $I_{max}$ be the interval with max_start and $I_{min}$ be the interval with min_end.

Statement: All intervals overlap each other if and only if all intervals contain max_start and min_end

Proof: (<-) This direction is easy. If all intervals contain max_start and min_end, then they all overlap each other at max_start and min_end.

(->) (Using Contraposition) Suppose some interval $I$ does not contain max_start. We also know that start time of $I$ is smaller than max_start. It means that it will not overlap with $I_{max}$ since it will end earlier than $I_{max}$. Similarly, you can show that if an interval does not contain min_end, it will not overlap with $I_{min}$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ The <- direction is actually a bit more tricky: you have to show that also $max\_start\le min\_end$. Its not hard to prove this, but I think its important $\endgroup$
    – nir shahar
    Aug 30, 2021 at 23:18
  • $\begingroup$ @nirshahar Thanks for going through the answer. But I did not understand why $max \_start \leq min\_end$ is required? $\endgroup$
    – Inuyasha Yagami
    Aug 31, 2021 at 4:35
  • $\begingroup$ Oh, my bad. Looking again at your answer - I think I was confused why we need both $max\_start$ and $min\_end$. Which for some reason made me assume you stated that the intervals overlap iff they overlap the entire interval $[max\_start, min\_end]$. In this case, this interval would be empty if $max\_start > min\_end$ $\endgroup$
    – nir shahar
    Aug 31, 2021 at 11:15
  • $\begingroup$ @nirshahar I think having $max\_start$ or $min\_end$ is also sufficient. $\endgroup$
    – Inuyasha Yagami
    Aug 31, 2021 at 16:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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