Efficient way to count number of intersections of line segments 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.
EXAMPLE INPUT: 
5 
7 8 
8 9 
0 3 
2 7  
10 15
EXAMPLE OUTPUT: 
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][0] &lt;= data[j][0]:
                left = data[i]
                right = data[j]
            else:
                left = data[j]
                right = data[i]
            
            if right[0] &lt;= left[1] &lt;= right[1]:
                counter += 1
            elif left[0] &lt;= right[0] &lt;= left[1]:
                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?
Let's first assume there is no common boundaries between all segments.
Create the list of tuples ($pos$, $ind$) with a value ($pos$) for each boundary of every segment (thus $2n$ values) and $ind$ the index of the segment, sorted by $pos$. Sorting is achieved in $O(n \log(n)).$
Keep two counters, $open$, the number of opened segments and $close$, the number of closed segments. Both are initially at 0.
$E[i]$ will be an array of the segment $i$ state, where 0 means not opened yet, 1 otherwise.
$A[i]$ will be the $n$-element array to output, which are 0s initially.
Then loop through the list,
for tuple (pos, i),
    if E[i] == 0, then A[i] = close, open += 1, E[i] = 1
    else A[i] = open-A[i]-1, close += 1

The &quot;-1&quot; stands for a segment not counting himself.
This achieves $O(n)$, then still driven by the sorting $O(n \log(n))$.
Now, how to treat common boundaries ? In your exemple, I understand that segments are closed and for example [2, 7] does intersect [7, 8]. A simple way to do it (clearly not the most efficient but still $O(n)$), is to loop 3 times on the tuples at the same position:

first, you only count the opening segments in $open$
then, you only update $E[i]$ and $A[i]$ for both opening and closing segments
finally, you only count the closing segments in $close$ (that now have $E[i] = 2$)