Количество пересечений отрезков

N, segments = 6, [
    (3, 5),
    (0, 10),
    (4, 8),
    (6, 8),
    (4, 12),
    (9, 9),
]
 
K = 0
for i in range(N):
    for j in range(i + 1, N):
        if segments[i][1] >= segments[j][0]\
        and segments[j][1] >= segments[i][0]:
            K += 1
 
print(K)

from bisect import bisect_right
 
N, segments = 6, [
    (3, 5),
    (0, 10),
    (4, 8),
    (6, 8),
    (4, 12),
    (9, 9),
]
# Сортировка по первой координате, затем по второй.
segments = sorted(segments)
 
# Первые координаты отрезков.
begin_coords = [segment[0] for segment in segments]
 
 
# Количество отрезков, не пересекающихся с отрезком номер i.
def count_not_intersecting_with_i(i):
    end_coord = segments[i][1]
    index = bisect_right(begin_coords, end_coord)
    return N - index
 
 
# Максимальное количество пересечений (если нет непересекающихся отрезков).
# По формуле суммы арифметической прогрессии.
intersects_max = N * (N + 1) // 2
 
print(intersects_max - sum(map(count_not_intersecting_with_i, range(N))))

segments = [
    (3, 5),
    (0, 10),
    (4, 8),
    (6, 8),
    (4, 12),
    (9, 9),]
 
segments.sort()
res = 0
cur_seg_counter = 0
n = segments[0][0]
while segments:
    for seg in segments:
        if seg[0] == n:
            res += cur_seg_counter
            cur_seg_counter += 1
 
    for seg in segments:
        if seg[1] == n:
            segments.remove(seg)
            cur_seg_counter -= 1
    n += 1
print(res)

import bisect
 
segments = [
    (3, 5),
    (0, 10),
    (4, 8),
    (6, 8),
    (4, 12),
    (9, 9), ]
 
segments.sort()
res   = 0
tails = []
for seg in segments:
    while len(tails) and tails[0] < seg[0]:
        tails.pop(0)
    res += len(tails)
    bisect.insort(tails, seg[1])
print(res)

import bisect
 
segments = [
    (3, 5),
    (0, 10),
    (4, 8),
    (6, 8),
    (4, 12),
    (9, 9), ]
 
segments.sort()
res = 0
tails = []
ind = 0
for seg in segments:
    while ind < len(tails) and tails[ind] < seg[0]:
        ind += 1
    res += len(tails) - ind
    bisect.insort(tails, seg[1])
print(res)

import heapq
 
INFINITY = 2111111111
 
segments = [
    (3, 5),
    (0, 10),
    (4, 8),
    (6, 8),
    (4, 12),
    (9, 9), ]
 
segments.sort()
res = 0
tails = [INFINITY]
for seg in segments:
    tail = heapq.heappop(tails)
    while tail < seg[0]:
        tail = heapq.heappop(tails)
    res += len(tails)
    heapq.heappush(tails, tail)
    heapq.heappush(tails, seg[1])
 
print(res)

import bisect
import heapq
 
segments = [
    (3, 5),
    (0, 10),
    (4, 8),
    (6, 8),
    (4, 12),
    (9, 9), ]
 
segments.sort()
res   = 0
tails = []
for seg in segments:
    while len(tails) and tails[0] < seg[0]:
        heapq.heappop(tails)
    res += len(tails)
    heapq.heappush(tails, seg[1])
print(res)

import heapq
import math
 
segments = [
    (3, 5),
    (0, 10),
    (4, 8),
    (6, 8),
    (4, 12),
    (9, 9), ]
 
segments.sort()
res   = 0
tails = [math.inf]
heapq.heapify(tails)
for seg in segments:
    while tails[0] < seg[0]:
        heapq.heappop(tails)
    res += len(tails) - 1
    heapq.heappush(tails, seg[1])
print(res)