Как создать оптимальное решение этой конфликтной проблемы?

Question

Предположим, что вы защищаете пляж от линейных кораблей различной длины с помощью рельсовых орудий, которые уничтожат все по прямой линии. Линейные корабли находятся на сетке ax, y и имеют параметры (x1, x2, y) для двух сторон и координаты y. У вас есть только ограниченные ресурсы, и вам нужно попробовать потопить все линейные корабли с наименьшим количеством железнодорожных орудий, которые будут размещены в координатах х.

Линейный корабль уничтожается, если x1 <= x <= x2, и все линейные корабли имеют высоту 1. </p>

В настоящее время у меня есть решение: добавить рельсовые орудия в позиции, которая тонет большинство кораблей, затем удалить эти корабли из списка и затем искать следующую позицию, которая тонет большинство кораблей в обновленном списке и так далее, пока не останется ни одного корабля. Однако я нашел контрпример к этому.

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

Answer 1

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

Сортировать начало и конечные sh x-координаты вместе с соответствующими индексами корабля.

Пройти по списку конечных sh. Если индекс текущего элемента отмечен - игнорируйте его, в противном случае отметьте индексы для всех начальных элементов до текущей координаты и стреляйте по текущей координате.

Для данного примера вы будете стрелять по 3, 6 и 8

Три списка / массива. Один содержит пары (start[i]; i), другой - пары (end[i]; i), третий - boolean[N] для отметок.

Первый элемент в конечном списке - 3 для корабля (0,3,1). Таким образом, мы стреляем и убиваем (отмечаем) корабли (0,3,1), (1,4,0) и (1,4,4), потому что их старты меньше 3.