# algorithms – 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.