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\$.
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.
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.
2 3 1 10 5 5 7 7 2 1 1 2 2
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 > holder: 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.