Counting intersections of wires between towers

Question

The "Rope Intranet" problem from Google Codejam 2010 asks us to count the number of intersections (black circles) in a planar straight-line graph like this:

That is, with each line segment having one endpoint with \$x=x_0\$ and the other with \$x=x_1\$.

Input

The first line of the input gives the number of test cases, \$T\$. \$T\$ test cases follow. Each case begins with a line containing an integer \$N\$, denoting the number of wires you see.

The next \$N\$ lines each describe one wire with two integers \$A_i\$ and \$B_i\$. These describe the windows that this wire connects: \$A_i\$ is the height of the window on the left building, and \$B_i\$ is the height of the window on the right building.

Output

For each test case, output one line containing "Case #\$x\$: \$y\$", where \$x\$ is the case number (starting from 1) and \$y\$ is the number of intersection points you see.

Sample input

2
3
1 10
5 5
7 7
2
1 1
2 2

Sample output

Case #1: 2
Case #2: 0

I have a working solution, but the time complexity is awful. Here is my code:

def solve(wire_ints, test_case):
    answer_integer = 0
    for iterI in range(number_wires):
        for iterJ in range(iterI):
            holder = [wire_ints[iterI], wire_ints[iterJ]] 
            holder.sort()
            if holder[0][1] > holder[1][1]:
                answer_integer = answer_integer + 1
    return("Case #" + str(test_case) + ":" + " " + str(answer_integer))

for test_case in range(1, int(input()) + 1):
  number_wires = int(input())
  wire_ints = []
  for count1 in range(number_wires):
    left_port,right_port = map(int, input().split())
    wire_ints.append((left_port,right_port))
  answer_string = solve(wire_ints, test_case)
  print(answer_string)

I was wondering if anyone here is able to suggest a way in which I can speed up my algorithm? After 4 hours I really can't see one and I'm losing my miinnnnddd.

Answer 1

There are two key observations to make about this problem.

The first (which you spotted), is that the exact heights of the left and right endpoints of each line segment don't matter, only their order. That is, a line \$A_i, B_i\$ intersects the line \$A_j, B_j\$ if either \$A_i < A_j\$ and \$B_i > B_j\$, or \$A_i > A_j\$ and \$B_i < B_j\$.

The second, is that each pair of intersecting lines is an "inversion". (An inversion is a pair of items that are out of order with respect to a permutation.) That is, if we start with the lines in order of their left heights \$A_i\$, and consider sorting them into the order of their right heights \$B_i\$, the number of intersections is the same as the number of inversions with respect to the sorted order.

The number of inversions in a sequence with respect to a sorted order can be counted in \$O(n \log n)\$ using an adaptation of the merge sort algorithm. This is a standard exercise in an algorithms course (for example, it's exercise 2–4d in Introduction To Algorithms by Cormen, Leiserson, Rivest, and Stein), so I won't spoil it for you here.