【LeetCode】3025. 人员站位的方案数 I（康复-T2）

题目描述

人员站位的方案数 I

问题描述

根据题意，要挨个寻找成对的对角点，从直观分析，

1. 挨个成对遍历
2. 判断算法属于对角条件
3. 判断其他节点是否在对角点的范围内

这种属于三重循环，换个思路。
以一个点为基准，判断有哪些节点是满足该基准节点的右下角对角点，然后再判断对角点间是否重叠

代码

v1

思路解析，先二重循环遍历，遍历每一对节点，使用一个二维数组记录每一个节点的满足右下角的节点。然后将节点是右下角节点判读是否覆盖

class Solution {
public:
    bool ifCorners(vector<int> p1,vector<int> p2)
    {
        if(p1[0]<=p2[0] &&p1[1]>p2[1]) return true;
        else if(p1[0]<p2[0] &&p1[1]==p2[1]) return true;
        return false;
        
    }
    int numberOfPairs(vector<vector<int>>& points) {
        int N = points.size();
        int count = 0;
        vector<vector<int>> corner_vec;
        for(int i=0;i<N;i++)
        {
            vector<int> tmp;
            for(int j=0;j<N;j++)
            {
                if(j==i) continue;
                if(points[i]==points[j]) continue;    //相等排除
                if(ifCorners(points[i],points[j])) tmp.push_back(j);
            }
            corner_vec.push_back(tmp);
        }
        //获得对角关系
        for(int i=0;i<N;i++)
        {
           
            if(corner_vec[i].size()==0) continue;
            if(corner_vec[i].size()==1) {count++;continue;}
            sort(corner_vec[i].begin(),corner_vec[i].end(),[&](int a,int b){
                return points[a][0]<points[b][0]|| (points[a][0]==points[b][0]&&points[a][1]>points[b][1]);
            });
            int aim_idx = 0;
            for(int j=1;j<corner_vec[i].size();j++)
            {
                
                int p1=corner_vec[i][aim_idx];
                int p2=corner_vec[i][j];
                if(points[p1][0]<points[p2][0] && points[p1][1]<points[p2][1]){
                     count++;
                     aim_idx = j;
                }
            }
            count++;   
        }
        return count;
    }
};

v2

对点集进行排序，满足条件x1<x2,y1>y2，进行排序，然后最左上角进行依次遍历
设置一个节点的更新边界，用于判断是否满足对角点的所有条件
以点为基准，第二个节点是b，同时更新下边界，第三个节点是a，其不在边界范围，排除，第三个节点是c，在上下边界范围内，然后进一步更新下边界。
总之就是，一步一步更新对角节点的上下边界。

class Solution {
public:
    int numberOfPairs(vector<vector<int>>& points) {
        int N=points.size();
        sort(points.begin(),points.end(),[](auto& p1,auto& p2){
            return (p1[0]<p2[0]) || (p1[0]==p2[0] && p1[1] > p2[1]);
        });
        int count = 0;
        for(int i=0;i<N-1;i++)
        {
            auto p = points[i];
            int y_b= INT_MIN;
            int y_p = p[1];
            for(int j=i+1;j<N && y_b < y_p;j++)
            {
                if(points[j][1] > y_b && points[j][1] <= y_p)
                {
                    y_b = points[j][1];
                    count++;
                }
            }
        }
        return count;
        
    }
};