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.