On my computer science course's exam I was given the following task:
You are given $n$ segments that lies on the same line: $i$-th segment starts at coordinate $from_i$ and ends at $to_i$. Your task is for each segment count number of other segments that intersects it.
2 1 1 2 0
I've implemented the naive algorithm:
def count_intersections(i): counter = 0 for j in range(len(data)): if i != j: if data[i] <= data[j]: left = data[i] right = data[j] else: left = data[j] right = data[i] if right <= left <= right: counter += 1 elif left <= right <= left: counter += 1 return counter n = int(input()) data =  for i in range(n): data.append(tuple(map(int, input().split()))) for i in range(n): print(count_intersections(i), end = ' ')
As you can see, I just iterate through eacher other segment and increment counter if it intersect the given one. Time complexity of my solution is $O(n^2)$. And because of this I got Tme Limit Error.
Do you know more efficient solution? Maybe some extraordinal Data Structure?