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.
As pointed out by the other answer, producing a list of the intersections is not doable in subquadratic time.
However, counting all the intersections can be done in linear time.
The rough idea for that one is to sort all coordinates (starting points and end points of intervals) into one list using counting sort (as the range of the values we are sorting is fixed) and iterate over it, maintaining a counter for the number of intervals intersecting at the current point and another one for the total number of intersections.
If the current coordinate is an end point, reduce the first counter by 1.
Otherwise (i.e. the current coordinate is a starting point), increase the first counter by 1 and increase the total counter by the value of the first counter.