Задача: Конференц-залы II.
https://t.me/pythonlСложность задачи: Средняя
Условие задачи:
Дан массив интервалов времени проведения совещаний, intervals, где intervals[i] = [start(i), end(i)]. Найдите минимальное требуемое количество конференц-залов.
Пример:
Ввод: intervals = [[0,30],[5,10],[15,20]]
Вывод: 2
Ввод: intervals = [[7,10],[2,4]]
Вывод: 1
Алгоритм решения задачи:
Номера интервалов дают хронологический порядок
Когда происходит конечное событие, должно быть начальное событие, которое произошло до этого, где «произошло до» определяется хронологическим порядком, заданным интервалами.
Совещания, которые начались, но еще не закончились, должны быть помещены в разные комнаты для совещаний, а количество необходимых комнат равно количеству таких встреч.
Например, у нас есть встречи, которые охватывают время следующим образом:
|_____|
|______|
|________|
|_______|
Затем массив времени начала и массив времени окончания после сортировки выглядят следующим образом:
|| ||
| | | |
Изначально endItr указывает на первое конечное событие, и мы перемещаем i, который является указателем начального события. Изучая начальные события, мы обнаружим, что первые два начальных события происходят до конечного события, на которое указывает endItr, поэтому нам нужны две комнаты (мы волшебным образом создали две комнаты), как показано переменной room. Затем, когда i указывает на третье начальное событие, мы обнаружим, что это событие происходит после конечного события, на которое указывает endItr, тогда мы увеличиваем endItr так, чтобы оно указывало на следующее конечное событие. То, что здесь происходит, можно представить себе как завершение одной из двух предыдущих встреч, и мы переместили только что начатую встречу в эту свободную комнату, поэтому нам не нужно увеличивать комнаты в это время и перемещать оба указателя вперед.
Затем, поскольку endItr переходит к следующему конечному событию, мы обнаружим, что начальное событие, указанное i, происходит до конечного события, указанного endItr. Таким образом, сейчас у нас начато 4 заседания, а закончилось только одно, поэтому нам нужна еще одна комната. И так продолжается.
