最大非支配集的算法

Question

找出下一个问题的算法:给定2D平面中n个点的集合S,如果x1> x2且y1> y2,则点(x1,y1)支配另一个点(x2,y2).找到最大的点集M,使得M是S的子集,并且没有M的点由S的另一个点支配.

Answer 1

通过增加x坐标对所有点进行排序.如果两个点具有相同的x坐标,则通过减小y坐标对它们进行排序.现在,可以看出点的子集是不可支配当且仅当他们的y坐标是在我们的排序顺序不增加,这意味着每个y坐标小于或等于前一个子序列.

所以算法将是:

1. 如上所述对点进行排序.时间:O(n*logn).
2. 找到y坐标的最长非增加子序列.时间:O(n*logn).这可以通过调整算法来找到最长的增长子序列来完成.

这给出了O(n*logn)中可能的最大集合.