在二维空间中，给定一堆矩形，每个矩形都覆盖多个点，并且对于指定的K个数，两个任意矩形之间可能存在重叠，我如何才能找到k个矩形，以使它们的并集覆盖最大个数。点？在此问题中，如果一个点被两个以上的矩形覆盖，则该点仅被计数一次，我们假设矩形的位置和大小以及点的位置是固定的，如输入中所给。
有人可以给我解决算法吗？或指出可以将其简化为某些已知问题？
这看起来像是“ 最大覆盖率问题”的几何版本，它与“ 设置覆盖率问题”密切相关，并且这两个是NP- Complete。
当然，您将集合设为矩形的特殊情况可能仍然适用于精确的多项式时间算法，但我对此表示怀疑。也许以上论文中的参考文献可能会为您提供一个好的解决方案。
希望有帮助！
