Я предполагаю, что у вас есть фиксированные прямоугольники (то есть вы не можете выбирать, насколько велики ваши прямоугольники и где они расположены). Если бы вы могли выбрать размер прямоугольников, проблема была бы тривиальной. Если бы вы могли выбрать, где расположить свои прямоугольники, это также было бы другой проблемой (решаемой другим жадным алгоритмом).
Для получения более подробной информации вы должны сообщить нам, как указаны ваши прямоугольники и точки и как они хранятся - или вам нужна помощь в выборе хорошей структуры данных с учетом вашего формата ввода.
Теперь, жадное решение вашей проблемы - действовать следующим образом. Сначала начните со всех "прямоугольников", выбранных в качестве точек покрытия. Затем один за другим удалите прямоугольник, покрывающий наименьшее количество точек, пока в вашем наборе не останется только K прямоугольников. Сложность этого алгоритма является полиномиальной, а его эффективность зависит от того, как вы собираетесь реализовать запрос «выяснить, какой прямоугольник покрывает наименьшее количество точек». Используя кучу, вы можете сделать это в O (1), с фазой предварительной обработки, чтобы построить кучу (сложность которой будет зависеть от того, как хранятся ваши очки).
РЕДАКТИРОВАТЬ : проблема с этим решением состоит в том, что на каждом шаге ответ на вопрос «сделаю так, чтобы у меня было наименьшее количество непокрытых точек» не является уникальным, несколько прямоугольников могут на этом этапе заполните критерий; в итоге может оказаться, что один выбор был бы лучше другого, и это не могло быть определено на этом этапе ...
/---------\
|2 |
/-----\ /-------\
|1 | *| |* | 3|
\-----/ \-------/
| |
\---------/
Например, здесь все прямоугольники связаны: если вы удалите один прямоугольник, вы не найдете точек. Однако очевидно, что наилучшее 1-решение состоит в том, чтобы прямоугольник 2 покрывал точки (обратите внимание, что прямоугольники 1 и 3 могут быть произвольно широкими, поэтому размер не является определяющим фактором).