Задача с собеседования в ШАР Яндекса

Большинство кандидатов на собеседовании в Школу Аналитиков-Разработчиков просто ВАЛЯТСЯ на алгосах, которые яндекс принципиально ставит в начало собеседования, и уже после них шли теорвер и кейс по аналитике. Если кандидат не решает алгос, ему даже не давали шанса пройти дальше. Это очередной повод задуматься над тем, что алгосы все-таки надо заботать, а сделать это приятнее всего можно на наших курсах.

Даны два списка интервалов, когда пользователь A и пользователь B были онлайн. Нужно найти все интервалы, когда оба были онлайн одновременно.

Решение:
Легчайшая задача на два указателя
Поскольку интервалы уже отсортированы по началу, мы можем использовать два указателя и пройти списки одновременно, сравнивая текущие интервалы

def intersect_intervals(a, b):
i = j = 0
result = []

while i < len(a) and j < len(b):
a_start, a_end = a[i]
b_start, b_end = b[j]

start = max(a_start, b_start)
end = min(a_end, b_end)

if start < end:
result.append((start, end))

if a_end < b_end:
i += 1
else:
j += 1

return result

Асимптотика O(N)

@algoses