A binary search tree of intervals, keyed on the low ends, where each node also knows the largest high end below it. That one number lets an overlap search skip whole subtrees.
This interactive visualization needs JavaScript.