Fast extraction of pairs overlapping an interval
This is a standard geometric data structure problem, which can be solved by storing the intervals $(x_1, y_1), \dots, (x_n, y_n)$ in an interval tree.  Then you can extract all the intervals $(x_i,y_i)$ overlapping a given query interval $(X,Y)$ in $O(\log n + k)$ time, where $k$ is the number of output intervals.