Count number of intervals containing another interval?

Question

Given two lists each containing N intervals (subset of the number line), each interval with form of a start point and endpoint. How many pairs of these intervals from one list contains intervals from another list?

For example:

If list A is {(1,7), (2,9)} and list B is {(3,6), (5,8)}

Then the count of pairs where A has an interval that contains an interval in B would be 3 pairs:

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

The goal is to shoot for O(n log n).

My algorithm currently is to sort by x-coordinate first and take that as one list. Then sort the list by y-coordinate and count the inversions between the two lists. But my question is why does this work? Any insight would be appreciated.

The way I have I'm currently visualizing is in the following geometric fashion (where each intersection of the lines is a count of the num inversion):

Note: I'm not sure how to go about checking inversions in a list of list. Just trying to get an approach that would give O(n log n). If there are any other approaches happy to hear suggestions.

Answer 1

I'll answer the first question about why the solution with inversion works. Firstly, I'll clarify one thing. You shouldn't count all inversions (intersections of lines) but only these that occur between an element from A list and an element from B list. In your example there is no difference but let's assume that A = {(1,7), (2,5)} and B = {(3,6), (5,8)}. If we visualize these case as in your example there would be 2 intersection but there is only 1 pair we are looking for i.e. (1,7), (3,6).

Now let's assume that we have 2 intervals: I1=(x1,y1) and I2=(x2,y2). I2 is included in I1. It means that x1 <= x2 and y1 >= y2. Now, if you sort the list of intervals by x then I1 will always be before I2. Analogically if you sort the list of intervals by y then I1 will always be after I2. It also beans that if we connect I1, I2 in the first list with I1, I2 in the second list then the lines must cross.

However, let's assume that x1 <= x2 and y1 < y2. Now I1 will be before I2 in the first and in the second list. If we connect I1, I2 in the first list with I1, I2 in the second list then the lines will never cross. The same situation is if x1 > x2 and y1 >= y2

Here is the visualization of these cases: