题解 | #病毒扩散#

一.题目描述
NC539病毒扩撒
牛牛刚刚得知牛牛所在的街道上有一个人得了新型冠状病毒！！！由于新型冠状病毒传染力很强，所以，只要在被传染的人的活动范围内活动都有可能被感染！现根据大数据可以得知，初始患病人在整个街道人群中的序号Pid和每个人在街道上的活动区域Pos。因为情况紧急，所以牛牛想请你帮忙快速计算下究竟最坏情况下会有多少人感染上冠状病毒？
图片说明
对样例解释：输入的整数表示第i(从0开始)个人是患者，也就是患者的范围是[2,3],所以序号0的人也会被感染，也就是最坏有3个人感染
二.算法(贪心)

首先题目意思看明白可以理解为最坏多少人感染就是找到区间交集的最大值，对于找区间交集的最大值我们很容易就可以想到可以采用贪心的思想，按照左端点从小到大排序，维护右界的最大值，我们就可以知道每一段连续的区间包含了多少个有交集的线段，再看患者的线段在哪一段就可以找出最大值了，下面是完整代码：

class Solution {
public:
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        int len=PeoplePosition.size();
        Point one=PeoplePosition[Personid];
        //对线段进行排序(下标从小到大排序) 为了可以进行贪心
        sort(PeoplePosition.begin(),PeoplePosition.end(),[](Point a, Point b) {return a.x<b.x;});
        int last=-1,cn=0,ck=0;
        //last表示右边界
        //cn记录个数
        for(int i=0;i<len;i++){
            if(PeoplePosition[i].x>last){
                if(ck) break;
                cn=1;
                last=PeoplePosition[i].y;
            } else {
                last=max(last,PeoplePosition[i].y);
                cn++;
            }
            //已经找到了患者的区间 后续就不需要进行右边界维护了
            if(PeoplePosition[i].x==one.x&&PeoplePosition[i].y==one.y){
                ck=1;
            }
        }
        return cn;
    }
};

时间复杂度： $O(nlogn)$ 只需要对数组进行一次遍历
空间复杂度： $O(1)$ 不需要额外空间
优缺点：需要想到贪心，但是代码实现简单
三.算法(并查集)
理解题目意思可以想到利用并查集，将所有区间进行随机合并，最后找到包含Personid的区间共由区间组成。思路很清晰，下面是完整代码：

 * struct Point {
 *    int x;
 *    int y;
 *    Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    int p[500005];
    int cn[500005];//表示合并区间的小区间个数
    //并查集的查
    int find(int x){
        if(p[x]==x) return x;
        return p[x]=find(p[x]);
    }
    //并查集的并
    void Union(int x,int y){
        int t1=find(x);
        int t2=find(y);
        if(t1==t2) return ;
        p[t1]=t2;
        cn[t2]+=cn[t1];
    }
    //判断两个区间是否有交集
    bool check(Point a,Point b){
        if (a.x<b.x)
            return b.x<=a.y;
        return a.x<=b.y;
    }
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        int len=PeoplePosition.size();
        //开始的初始化
        for(int i=0;i<=len;i++){
            p[i]=i;
            cn[i]=1;
        }
        //双重循环找到相交的区间合并
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(check(PeoplePosition[i],PeoplePosition[j])){
                    Union(i,j);
                }
            }
        }
        //返回最后的个数
        return cn[find(Personid)];
    }
};

时间复杂度： $O(n^{2}logn)$ 对于n次循环每一次的复杂度是 $O(logn)$
空间复杂度： $O(n)$ 需要额外空间来维护并查集
优缺点：时间复杂度高，但是容易实现代码简单