Meeting Rooms

Q: Какова временная сложность задачи «Переговорные комнаты»?

Сортировка встреч по времени начала требует O(n log n) , а проход, в котором сравниваются соседние элементы, — O(n) , поэтому общая сложность составляет O(n log n) . Сравнение каждой пары вместо этого требует O(n²) .

Q: Почему достаточно сравнить каждую встречу с предыдущей?

После сортировки по времени начала, если до сих пор не было обнаружено конфликтов, встречи образуют цепочку, в которой каждая начинается в момент окончания предыдущей или позже. Последняя встреча в цепочке заканчивается позже всех. Новая встреча, которая начинается в момент её окончания или позже, не может пересекаться ни с одной из предыдущих.

Q: Считаются ли встречи с общей границей пересекающимися?

В этой задаче — нет: встреча может начаться ровно в тот момент, когда заканчивается другая. Поэтому проверка использует строгое условие start < previous end . Если бы встречи, соприкасающиеся по времени, были запрещены, проверка выглядела бы так: start ≤ previous end .

ЛегкоИнтервалы Сортировка

+10

Тебе дан список встреч в виде двух массивов: встреча i длится с starts[i] до ends[i]. Один человек хочет посетить все встречи, поэтому никакие две встречи не должны пересекаться. Встреча может начаться ровно в тот момент, когда заканчивается другая. Верни true, если человек может посетить каждую встречу, и false в противном случае.

Функция

canAttendMeetings(starts: integer-array, ends: integer-array) → boolean

startsinteger-array: время начала каждой встречи
endsinteger-array: время окончания каждой встречи с тем же индексом, что и время её начала
Возвращаетboolean: true, если никакие два собрания не пересекаются по времени, иначе false

Ограничения

1 ≤ starts.length == ends.length ≤ 5000
0 ≤ starts[i] < ends[i] ≤ 10⁶
Встречи не отсортированы. Две встречи могут быть одинаковыми.

Примеры

Ввод: starts = [9, 13, 10]ends = [10, 15, 12]
Вывод: true
Пояснение: В хронологическом порядке встречи проходят с 9 до 10, с 10 до 12 и с 13 до 15. Вторая начинается в тот же момент, когда заканчивается первая, а это допустимо, поэтому ответ — true.

Ввод: starts = [1, 4, 7]ends = [5, 6, 8]
Вывод: false
Пояснение: Встреча с 1 до 5 всё ещё продолжается в 4, когда начинается встреча с 4 до 6, поэтому ответ — false.

Дополнительный вопрос

Если встречи бронируются по одной, как проверять каждую новую бронь по расписанию за O(log n), не сортируя всё заново?

Решение

Проверка каждой пары встреч позволяет обнаружить любые пересечения, но требует O(n²). Сортировка по времени начала меняет задачу: после сортировки встреча может пересекаться только со своей соседней встречей, поэтому достаточно одного сравнения на каждую встречу.

Сравните каждую пару

Верно, но не успевает на самых больших тестах

Идея

Две встречи пересекаются, если каждая из них начинается до окончания другой. Для встреч с 1 до 5 и с 4 до 6: 1 меньше 6, а 4 меньше 5, поэтому они пересекаются. Для встреч с 9 до 10 и с 10 до 12: 10 не меньше 10, поэтому они только соприкасаются.

Использование строгого < с обеих сторон позволяет встрече начинаться точно в момент окончания другой. Выполните проверку для каждой пары и верните false при первом пересечении.

Проблема в количестве пар. Для n = 5000 встреч получится около 12,5 миллиона пар, и при расписании без пересечений придётся проверить их все, что слишком медленно для самых больших тестов.

Алгоритм

Для каждого индекса i и каждого следующего за ним индекса j:
Если starts[i] < ends[j] и starts[j] < ends[i], две встречи пересекаются: верни false.
Если ни одна пара не пересекается, верни true.

def canAttendMeetings(starts, ends):
    n = len(starts)
    for i in range(n):
        for j in range(i + 1, n):
            # two meetings clash when each one starts before the other ends
            if starts[i] < ends[j] and starts[j] < ends[i]:
                return False
    return True

Отсортируйте по началу и проверьте соседние элементы

Идея

Отсортируй встречи по времени начала, сохранив соответствие каждого времени начала его времени окончания. Теперь возьми любую встречу и ту, что идет непосредственно перед ней. Если более ранняя встреча заканчивается после начала более поздней, они пересекаются. Если нет, более поздняя встреча начинается в момент окончания более ранней или позже.

Почему нужно проверять только соседнюю встречу? Если каждая встреча до текущей начинается в момент окончания предыдущей встречи или позже, то они не пересекаются, а встреча непосредственно перед текущей заканчивается последней. Новая встреча, которая начинается в момент ее окончания или позже, начинается в момент окончания всех этих встреч или позже.

В первом примере отсортированные встречи идут с 9 до 10, с 10 до 12 и с 13 до 15. Начало в 10 не раньше окончания в 10, а начало в 13 не раньше окончания в 12, поэтому пересечений нет. Встречи с одинаковым временем начала всегда пересекаются, поскольку каждая встреча длится как минимум одну единицу времени, и эта проверка тоже обнаруживает их.

Сортировка занимает O(n log n), а проход — O(n). Копия встреч с сохранением пар занимает O(n) памяти.

Алгоритм

Сопоставьте каждое начало с его концом.
Отсортируйте пары по времени начала.
Для каждой встречи после первой сравните её начало с окончанием предыдущей встречи.
Если время начала меньше, верните false.
После цикла верните true.

def canAttendMeetings(starts, ends):
    meetings = sorted(zip(starts, ends))  # by start time
    for i in range(1, len(meetings)):
        # a meeting must not start before the one right before it ends
        if meetings[i][0] < meetings[i - 1][1]:
            return False
    return True

Ловушки и крайние случаи

Типичные ошибки связаны с тем, какие концы сравниваются и как обрабатываются соприкасающиеся встречи.

Сортировка starts при сохранении ends в исходном порядке. Каждый конец должен перемещаться вместе со своим началом, иначе вы сравните начало с концом другой встречи.
Использование ≤ вместо <. Встречи с 9 до 10 и с 10 до 12 соприкасаются, но не пересекаются, и для них ответ — true.
Проверка только того, что каждая встреча заканчивается до начала следующей во входном порядке. Входные данные не отсортированы, поэтому соседние элементы в них ничего не говорят.
Запись проверки пары с одним условием, например starts[j] < ends[i]. Она работает только когда встреча j начинается позже; для встреч с 5 до 6 и с 0 до 1 именно в таком порядке условие 0 < 6 сообщает о конфликте, которого нет.

Частые вопросы3

Какова временная сложность задачи «Переговорные комнаты»?

Сортировка встреч по времени начала требует O(n log n), а проход, в котором сравниваются соседние элементы, — O(n), поэтому общая сложность составляет O(n log n). Сравнение каждой пары вместо этого требует O(n²).

Почему достаточно сравнить каждую встречу с предыдущей?

После сортировки по времени начала, если до сих пор не было обнаружено конфликтов, встречи образуют цепочку, в которой каждая начинается в момент окончания предыдущей или позже. Последняя встреча в цепочке заканчивается позже всех. Новая встреча, которая начинается в момент её окончания или позже, не может пересекаться ни с одной из предыдущих.

Считаются ли встречи с общей границей пересекающимися?

В этой задаче — нет: встреча может начаться ровно в тот момент, когда заканчивается другая. Поэтому проверка использует строгое условие start < previous end. Если бы встречи, соприкасающиеся по времени, были запрещены, проверка выглядела бы так: start ≤ previous end.

def canAttendMeetings(starts, ends):
    # Напишите код здесь

Тест #1

Тест #2

Аргументы

starts = [9, 13, 10]
ends = [10, 15, 12]

Ожидаемый вывод

true