Google CodeJam Past Exercise - Decrease runtime

Question

I have been working on a past Google Codejam algorithm from 2010, but the time complexity is awful.

Here is the question from Google Codejam: https://code.google.com/codejam/contest/619102/dashboard

TLDR - Imagine two towers that have a number line running up the sides, we draw a line from one buildings number line (say from 10) to another point on the other buildings number line (say from 1). If we do this n times, how many times will those lines intersect?

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.

Here is my code as of right now.

An example input would be:

2 - (Number of cases)

3 - (Number of wires in case # 1)

1 10

5 5

7 7

Case #1: 2 - (2 intersections among lines 1,10 5,5 7,7)

2 - (Number of wires in case #2)

5 5

2 2

Case #2: 0 - (No lines intersect)

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)

This algorithm does WORK for any input I give it, but as I said its very ugly and slow.

Help would be appreciated!

I think you'll get better answers at [codereview.se] – Rakete1111 Sep 03 '16 at 14:02 — Rakete1111, Sep 03 '16 at 14:02
It might also be off-topic here I think – Rakete1111 Sep 03 '16 at 14:04 — Rakete1111, Sep 03 '16 at 14:04

score 1 · Answer 1 · edited May 23 '17 at 12:01

Since N is 1000 an algorithm with O(N^2) would be acceptable. So what you have to do is sort the wires by one of their end points.

//sorted by first number
1 10    
5 5
7 7

Then you process each line from the beginning and check whether it has intersection with lines before it. If the second end point of a line before it is bigger than the second point of current line they have intersection. This requires two loops thus the O(N^2) complexity which suffice for N=1000.
Also you can interpret this as an inversion count. you have to count the number of inversions of the second end points where the list is sorted by first end point.

10 5 7 ->‌ number of inversions is 2, because of (10,5) and (10,7)

Also there is O(NlogN) approach to count the number of inversions which you don't need for this question.

Google CodeJam Past Exercise - Decrease runtime

1 Answers1