Мне недавно задали этот вопрос в интервью. Несмотря на то, что я смог подняться O (n²), интервьюер был одержим O (n) решение. Я также проверил несколько других решений O (N LOGN) который я понял, но O (n) решение до сих пор не моя чашка чая, которая предполагает встречи, отсортированные по времени начала.

Кто-нибудь может объяснить это?

Постановка задачи: Вам дано назначения. Каждое назначение содержит время начала и время окончания. Вы должны эффективно перенести все конфликтующие встречи.

Человек: 1,2, 3, 4, 5

Запуск приложения: 2, 4, 29, 10, 22

Конец приложения: 5, 7, 34, 11, 36

Ответ: 2x1 5x3O (n

 LOGN) алгоритм: отдельно начальная и конечная точка, как это:

2с, 4с, 29с, 10с, 22с, 5е, 7е, 34е, 11е, 36е

затем рассортируйте все эти пункты (для простотыПредположим, что каждая точка уникальна):

2с, 4с, 5е, 7е, 10с, 11е, 22с, 29с, 34е, 36е

если у нас есть последовательные запуски без концов, то это перекрытие: 2s, 4s смежны, так что перекрытие есть

Мы будем вести подсчет "S" и каждый раз, когда мы сталкиваемся с ним, +1, а когда встречается e, мы уменьшаем счет на 1.