Алгоритм по нахождению промежутков, не принадлежащих ни одному отрезку

Question

Даны координаты начала и конца отрезков, следует найти количество промежутков координатной прямой, не принадлежащих ни одному отрезку.

Код из аналогичной задачи про время:

n = int(input())

mtx = []

mintimeidx = 22222222222
maxtimeidx = -22222222222

for _ in range(n):
    c_expr = [x.split('.') for x in input().split()]

    times = [int(x[0])*60 + int(x[1]) for x in c_expr]
    mtx.append(times)

    mintimeidx = min(mintimeidx, times[0])
    maxtimeidx = max(maxtimeidx, times[1])

pline = [0]*24*60

start_time = 8*60
end_time = 20*60 + 1

for I in mtx:
    for K in range(max(I[0], start_time), min(I[1]+1, end_time)):
        pline[K] = 1

ccont = -1
answ = 0

for I in range(start_time, end_time):
    if (ccont != pline[I]):
        ccont = pline[I]
        if pline[I] == 0:
            answ += 1

if answ == 0:
    print('YES')
else:
    print('NO', answ)

Какие существуют более быстрые алгоритмы по решению данной задачи (или подобных)?

Answer 1

Алгоритм, работающий за O(nlogn), где n - количество временных промежутков, независимо от количества элементарных интервалов (ладно здесь минутные, а если секунды или микросекунды?):

Сложить в единый список пары (кортежи или списки), содержащие время и признак -1 для начала промежутка, +1 для конца промежутка. Добавить ещё пары для (8.00, +1) и (20.00, -1) для единоообразной обработки этих концов.

Отсортировать по полю времени (отрицательный признак начала обеспечивает то, что при одинаковом времени конца и начала не будет промежутка нулевой длины)

Счетчик активных промежутков cnt = -1

Пройти по списку по порядку, добавляя к cnt второе поле пар. Если cnt становится равным нулю - начался свободный промежуток, увеличиваем счётчик свободных.

Вот пример родственной задачи, только там считаются промежутки с наибольшим покрытием

n = int(input())

mtx = []

for i in range(n):
    c_expr = [x.split('.') for x in input().split()]

    times = [int(x[0])*60 + int(x[1]) for x in c_expr]
    mtx.append([times[0], -1])
    mtx.append([times[1], 1])

mtx.append([8*60, 1])
mtx.append([20*60, -1])

mtx.sort()

print(mtx)

cnt = -1
free = 0

for m in mtx:
    cnt += m[1]
    if cnt == 0:
        free += 1

print('свободных ', free)

БЛОГ НА HUSL

Алгоритм по нахождению промежутков, не принадлежащих ни одному отрезку

Ответы (1 шт):