小编Arn*_*old的帖子

我的问题是:我们在2D空间中有N个点,每个点都有一个正重量.给定由两个实数a,b和一个整数k的查询,找到大小AXB的矩形的位置,与边缘平行于轴线,这样的前k个点,即,k个点具有最高权重的总和矩形覆盖的权重最大化？

任何建议表示赞赏.

PS:有两个相关的问题已经得到很好的研究:

• 最大区域总和:找到总权重最大的矩形.复杂性:NlogN.
• top-K查询正交范围:找到给定矩形中的top-k个点.复杂度:O(log(N)^ 2 + k).