algorithm - 最大非支配集算法

Question

找到下一个问题的算法：给定二维平面中的 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) 中的最大可能集合。

Answer 2

有一种分治算法可以在 O(n*logn) 时间内完成此操作。

让我们根据它们的 x 坐标将这些点分成大小为 n/2 的两半。我们在两半中都找到了非支配点集。您需要观察在右半部分找到的所有非支配点都将存在于我们的最终列表中。

有了这个观察，我们可以编写我们的组合步骤，删除左半部分中所有 y 坐标小于右半部分非支配集中点的最高 y 坐标的非支配点。我们有一组非支配点。

算法：

Find the median along x axis - O(n) time
Find non-dominated points in the left half - T(n/2) 
Find non-dominated points in the right half - T(n/2)
set of non-dominated points could be on O(n) so, the combine step might have to check O(n) points

时间方程：

 T(n) = 2T(n/2) + O(n) which is O(n*logn)

您可以将其进一步改进为 O(n*logH)，其中 H 是非支配点的数量，它需要对问题有更深入的了解，并且它是您工作的一个很好的扩展。

Answer 3

#include <bits/stdc++.h>
using namespace std;

bool comp(pair<int,int> a,pair<int,int> b) {
    if(a.first<b.first)
        return true;
    else if(a.first==b.first) {
        if(a.second<b.second)
            return true;
        else
            return false;
    }
    return false;
}

int main() {
    int n,x,y;
    cin>>n;
    vector <pair<int,int>> points;
    vector <int> brr;
    for( int i=1;i<=n;i++ ) {
        cin>>x>>y;
        points.push_back({x,y});
    }
    if(n==1) {
        cout<<"1\n";
        return 0;
    }
    sort(points.begin(),points.end(),comp);
    priority_queue <int> point_y;
    for( int i=n-1;i>=0;i-- ) {
        while(!point_y.empty()) {
            if(point_y.top()>points[i].second)
                point_y.pop();
        }
        if(i>=1&&points[i].first==points[i-1].first) {
            brr.push_back(points[i].second);
        }
        else {
            point_y.push(points[i].second);
            for(int it : brr )
                point_y.push(it);
            brr.clear();
        }
    }
    cout<<point_y.size()<<endl;
}

这可能会帮助你..我正在做的是。首先对点进行排序(x1<x2) || (x1==x2&&y1<y2) ，然后从 priority_queue 中弹出的 end 进行迭代，其中 y 大于该点