Comment by joshlk

R-Trees are a good data structure to use in this case, enabling you to query a collection of intervals for overlap with another in O(log(n)) time.

Wikipedia: https://en.wikipedia.org/wiki/R-tree