Минимальное количество конференц-залов - PullRequest
0 голосов
/ 07 апреля 2020

Извинения, если такого рода вопросы здесь не разрешены.

Я сталкивался с таким вопросом: " Учитывая список интервалов, представляющих время начала и окончания 'N' собраний, найдите минимальное количество комнат, необходимое для проведения всех собраний. " , Я решил это, найдя максимальное количество пересекающихся интервалов.

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

Почему использование min heap более эффективно / идеальный ответ?

Оба решения имеют O (nlogn) временную сложность. Сложность пространства одинакова для обоих, мой ответ немного более эффективен, так как мне нужно только место для сортировки.

Я приложил оба ответа. Заранее спасибо

enter image description here

enter image description here

1 Ответ

2 голосов
/ 07 апреля 2020

Ваше решение выглядит хорошо с точки зрения сложности, но, похоже, просто не проходит тесты. Одна из причин - ваш кодовый блок «else», он сбрасывает все и начинает отсчет заново, но похоже, что он должен просто уменьшиться на единицу.

Итак, у вас есть тест с

start[0] = 0 end[0] = 1000 
start[1] = 0 end[1] = 1000 
start[2] = 1 end[2] = 2
start[3] = 3 end[3] = 10
start[4] = 5 end[4] = 6

произойдет сбой, потому что когда index = 2 и вы посещаете кодовый блок else, вы получите count = 1, но это неверно, потому что оно должно быть 2.

...