Какой алгоритм использовать для решения этой задачи?

Question

Недавно я столкнулся с тестом на собеседование в hackerrank, где я не смог правильно решить следующую задачу.Я бы не хотел называть точную проблему в целях конфиденциальности, но могу сказать, что в Google ее нигде не было с таким названием.

Проблема

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

Пример

N = 5
прибытие = [1, 3, 3, 5, 7] ( исполнители прибывают в это время)
продолжительность = [2, 2, 1, 2, 1] ( время, необходимое для завершения их выступлений)
решение = 4

Таким образом, в момент 1 мы можем принять исполнителя и закончим в момент 3.В момент времени 3 у нас есть два противоречивых выбора, и не имеет значения, какой из них мы выбрали.Время 5 и 7 также не конфликтуют.

Мое решение

1. Составлял кортежи прибытий и продолжительности с помощью архивирования.Сортировка кортежей сначала по прибытию, затем по продолжительности.
2. Внешний цикл for для i от начала до конца.Инициализируйте новый набор в каждом итерации.
3. Внутренний цикл for для j от i до конца.Проверьте, можно ли добавить j в набор без конфликта.Если заданный размер больше максимального, я сохраняю.

Исходный код Python

Вопросы

1. Есть ли лучшие способы, стандартные алгоритмы для решения этой проблемы?
2. Я знаю, что есть некоторые крайние случаи, для которых мой алгоритм не работает.Hackerrank оценил мой алгоритм, и он прошел всего 7/13 тестовых примеров.Какие могут быть крайние случаи, которые я упускаю?
3. Это проблема поиска или проблема оптимизации?

Answer 1

Это простой Максимизация интервального планирования проблема, которая может быть решена в O(n log(n)) время с помощью простого жадного алгоритма.Хитрость заключается в сортировке выступлений в соответствии с время окончания и не время начала.

Вот описание решения, найденного на странице Википедии, на которую я ссылался:

---

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

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

• Выбор кратчайших интервалов или интервалов с наименьшим количеством конфликтов также не является оптимальным.

Жадное полиномиальное решение

Следующий жадный алгоритм действительно находит оптимальное решение:

Select the interval, x, with the earliest finishing time.
Remove x, and all intervals intersecting x, from the set of candidate intervals.
Repeat until the set of candidate intervals is empty.

Всякий раз, когда мы выбираем интервал на шаге 1, нам, возможно, придется удалить много интервалов на шаге 2.Однако все эти интервалы обязательно пересекаются со временем окончания x, и, таким образом, все они пересекают друг друга.Следовательно, не более 1 из этих интервалов может быть в оптимальном решении.Следовательно, для каждого интервала в оптимальном решении существует интервал в жадном решении.Это доказывает, что жадный алгоритм действительно находит оптимальное решение.

Более формальное объяснение дается в Обвинительный аргумент.

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

---

Answer 2

Посмотрите на планирование с максимальным интервалом.

Назначьте интервал $(s_i, t_i)$ каждому исполнителю, за $i=1,\точек,N$, что означает , что представление начинается вовремя $s_i$ и имеет продолжительность в $t_i - s_i$.

Предположим пока, что все интервалы отсортированы по времени их окончания.Просто для простоты предположим также, что все времена различны (в этом предположении нет необходимости).Затем ваша проблема может быть решена в $O(N)$ время.

Рассмотреть $(s_1, t_1)$ и пусть $Я$ быть набором интервалов, которые пересекают его (исключая $(s_1, t_1)$ сам по себе).

Легко видеть, что все интервалы в $Я$ должен начаться раньше $t_1$ (поскольку в противном случае они бы не пересекались $(s_1, t_1)$) и закончится после $t_1$ (в противном случае $t_1$ это не было бы минимальным временем окончания).Это означает, что все интервалы в $I \cup \{ (s_1, t_1) \}$ пересекаются друг с другом, и, следовательно, любое решение может содержать не более одного из них.

Пусть $S$ быть решением (т.е. подмножеством попарно непересекающихся интервалов).Всегда можно преобразовать $S$ в новое решение $S'$ который содержит $(s_1, t_1)$ и такой , что $|S'| \ge |S|$.

Если $S \ cap I = \пустой набор$ тогда мы тривиально закончили, так как можем выбрать $S' = S \cup \{ (s_1, t_1) \}$ (обратите внимание, что это также включает случай, в котором $(s_1, t_1) \в S$).

Если $S \ cap I eq \emptyset$, пусть $(s_i, t_i)$ быть уникальным интервалом в $S \cap I$.Любой интервал $(s_j, t_j) \в S \setminus \{ (s_i, t_i) \}$ должен удовлетворять либо $s_j > t_i > t_1$ или $s_i > t_j > t_1$.Последний случай на самом деле невозможен, поскольку это противоречило бы тому факту, что $(s_i, t_i) \in S$.Другими словами, если мы заменим $(s_i, t_i)$ с $(s_1, t_1)$ мы все еще получаем осуществимое решение.Поэтому мы выбираем $S' = S \cup \{(s_1, t_1)\} \setminus \{ (s_i, t_i) \}$.

Суть в том, что всегда существует оптимальное решение, которое содержит $(s_1, t_1)$.Поэтому вы всегда можете добавить $(s_1, t_1)$ для вашего решения удалите все интервалы в $S \cup \{ (s_1, t_1) \}$, и ищите оптимальное решение среди оставшихся интервалов.Это равносильно запуску жадного алгоритма, который рассматривает интервалы по порядку и добавляет любой подходящий интервал.

Из вашего экземпляра кажется, что время начала уже отсортировано.В этом случае вы можете выполнить трюк с "обращением времени вспять", т. е. поменять местами время начала и окончания, например, изменив $(s_i, t_i)$ в $(-t_i, -s_i)$, что позволяет вам получить $O(N)$-временной алгоритм путем пропуска начального этапа сортировки, который уже потребовал бы $\Omega(N \log N)$ время.