Заметание прямой: почему можно разрывать пары «начало-конец»
Задача про минимальное число переговорок часто решается так:
def min_rooms(intervals):
starts = sorted(iv[0] for iv in intervals)
ends = sorted(iv[1] for iv in intervals)
best = active = 0
j = 0
for s in starts:
while j < len(ends) and ends[j] <= s:
j += 1
active -= 1
active += 1
best = max(best, active)
return best
Здесь начала и концы сортируются независимо, то есть связь «этот конец принадлежит этой встрече» теряется. Почему решение при этом остаётся корректным?
- Это работает только при условии, что все интервалы имеют одинаковую длину, иначе счётчик собьётся
- Ответ зависит только от максимума одновременно активных встреч, а он определяется порядком событий
- Это ошибка, дающая завышенный ответ: массивы обязательно надо сортировать как пары «начало-конец»
- Это работает, потому что после раздельной сортировки интервалы гарантированно перестают пересекаться