# Intervals Collision Detection Algorithm

Given a collection of non-empty intervals [a,b), where a/b are integers in some finite range (ex. 0...100) and a is less than b, can you find an algorithm that will detect all intervals that exhibit some collision/overlap where the worst-case performance of the algorithm is better than O(n^2)? You can assume that intervals starting at an end of another interval do not overlap, ex [15,22) and [22,30) do not overlap.

For example, given this collection {[12,16),[8,13),[16,34)} the result would be {0,1} because interval at index 0 intersects some interval, and interval at index 1 intersects some interval.

I have an algorithm that in worst case performs O(n^2) but can't figure out one that is faster. Mine doesn't use binary search trees, simply orders the intervals according to a, and then has a loop over all the elements with an inner loop on the remaining elements checking for intersection -- once an inner loop interval doesn't intersect the inner loop stops and the outer loop proceeds to the next element.

I am not looking for exact code, just a clear explanation of such an algorithm.

• @D.W. This problem is derived from an interview I had 2 weeks ago. The original problem dealt with events having a start date and an end date. You could assume that each event falls within the boundry of a single day, but this assumption doesn't change the nature of the problem, as each day can be considered an individual subproblem. What I didn't realize at the time is that one could naturally assume that the start/end dates would abide to an HHMM format, ignoring seconds and milliseconds, so the problem could be reduced to a range of [0,2400). Sep 27, 2020 at 20:09

• Because of the sorting, this not linear but $\Theta(n\log n)$. Sep 27, 2020 at 13:44