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.