algorithm - Count number of intervals containing another interval? -

given 2 lists each containing n intervals (subset of number line), each interval form of start point , endpoint. how many pairs of these intervals 1 list contains intervals list?

for example:

if list {(1,7), (2,9)} , list b {(3,6), (5,8)}

then count of pairs has interval contains interval in b 3 pairs:

(1,7),(3,6) (2,9)(3,6) (2,9)(5,8) 

the goal shoot o(n log n).

my algorithm sort x-coordinate first , take 1 list. sort list y-coordinate , count inversions between 2 lists. question why work? insight appreciated.

the way have i'm visualizing in following geometric fashion (where each intersection of lines count of num inversion):

note: i'm not sure how go checking inversions in list of list. trying approach give o(n log n). if there other approaches happy hear suggestions.

i'll answer first question why solution inversion works. firstly, i'll clarify 1 thing. shouldn't count inversions (intersections of lines) these occur between element list , element b list. in example there no difference let's assume a = {(1,7), (2,5)} , b = {(3,6), (5,8)}. if visualize these case in example there 2 intersection there 1 pair looking i.e. (1,7), (3,6).

now let's assume have 2 intervals: i1=(x1,y1) , i2=(x2,y2). i2 included in i1. means x1 <= x2 , y1 >= y2. now, if sort list of intervals x i1 before i2. analogically if sort list of intervals y i1 after i2. beans if connect i1, i2 in first list i1, i2 in second list lines must cross.

however, let's assume x1 <= x2 , y1 < y2. i1 before i2 in first , in second list. if connect i1, i2 in first list i1, i2 in second list lines never cross. same situation if x1 > x2 , y1 >= y2

here visualization of these cases: