# All 1D lines overlap each other

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.

Let $$I_{max}$$ be the interval with max_start and $$I_{min}$$ be the interval with 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}$$.
• 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 Aug 30, 2021 at 23:18
• @nirshahar Thanks for going through the answer. But I did not understand why $max \_start \leq min\_end$ is required? Aug 31, 2021 at 4:35
• 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$ Aug 31, 2021 at 11:15
• @nirshahar I think having $max\_start$ or $min\_end$ is also sufficient. Aug 31, 2021 at 16:02