Длина свободной части главного отрезка

Условие

Дан основной отрезок [start, finish] и произвольное количество вспомогательных отрезков. Требуется вычислить суммарную длину той части основного отрезка, где не происходит наложения ни одного из вспомогательных отрезков.

# start = 15, finish = 165
# seg1 [37, 68]
# seg2 [52, 74]
# seg3 [118, 146]
# seg4 [35, 44]
# seg5 [37, 65]
# seg6 [46, 74]

# Answer: 83

Ответ

Обрежьте вспомогательные отрезки границами основного, объедините пересечения и вычтите суммарную покрытую длину из finish − start.

def free_length(start, finish, segments):
    if finish < start:
        raise ValueError('Неверные границы')
    clipped = []
    for a, b in segments:
        if b < a:
            raise ValueError('Неверный отрезок')
        a, b = max(a, start), min(b, finish)
        if a < b:
            clipped.append((a, b))
    covered = 0
    right = start
    for a, b in sorted(clipped):
        covered += max(0, b - max(a, right))
        right = max(right, b)
    return finish - start - covered

В примере покрыты [35, 74] и [118, 146]: их длины 39 и 28. Свободно 150 − 67 = 83. Речь о геометрической длине, поэтому прибавлять единицу для включённых концов нельзя. Сложность — O(n log n).