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.