题解 | #病毒扩散#

思路：

题目的主要信息：

数组PeoplePosition是每个人活动的区间，Personid表示感染者的下标
所有感染者直接活动过的区间，或者与之直接相交的区间，或者与之间接交叉的区间（与前面两个的并集相交）都视作感染区间
活动范围与感染区间有交集的人视为感染者计数，求最后的感染人数
下标从0开始

方法一：贪心
具体做法：
依据贪心思想，首先按照区间起点从小到大排序，维护区间终点的最大值，我们就可以知道每一块连续的区间包含了多少个小区间，再看感染者下标在哪一块里。如果一块连续的区间都没有目标感染者，那我们更新res为1，重新计数。
图片说明

class Solution {
public:
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        int n = PeoplePosition.size();
        Point temp = PeoplePosition[Personid];
        //按照区间首排序
        sort(PeoplePosition.begin(), PeoplePosition.end(), [](Point& x, Point& y) {return x.x < y.x;});
        int right = -1; //记录区间最右值
        int res = 0; 
        bool flag = false; //有无遇到过感染者的区间
        for(int i = 0; i < n; i++){
            if(PeoplePosition[i].x > right){
                if(flag)  //大于维护的区间最大值且已经过了感染者区间
                    break;
                res = 1;
                right = PeoplePosition[i].y;
            }
            else{
                right = max(right, PeoplePosition[i].y); //区间右边增加
                res++;
            }
            if(PeoplePosition[i].x == temp.x && PeoplePosition[i].y == temp.y)
                flag = true;
        }
        return res;
    }
};

复杂度分析：

时间复杂度： $O(nlog_2n)$ ，遍历一次相对排序较小故忽略，sort函数快排为 $O(nlog_2n)$
空间复杂度： $O(1)$ ，常数级临时变量

方法二：并查集（超时）
具体做法：
这本来就是一道并查集的题。用并查集的方法虽然复杂度更高，但是这里提交显示时间更快。
我们可以构建一个并查集类DSU，通过不断合并两个任意下标的区间（如果它们有交集的话），将所有的小区间合并成大区间，最后找到包含Personid的区间共由多少小区间组成。
图片说明

#include <numeric>
class DSU{ //构建并查集的类
public:
    DSU(int n) : p(n), size(n, 1){ //初始化n个集合
        iota(begin(p), end(p), 0); //从0开始填充到n-1
    }

    int find(int x){
        if (p[x] == x) 
            return x;
        return p[x] = find(p[x]); //递归查找是否存在
    }

    void _union(int u, int v) {
        int pu = find(u); //相互找到最大关联是否统一
        int pv = find(v);
        if (pu == pv) //已经合并了
            return;
        p[pu] = pv;
        size[pv] += size[pu]; //合并
    }

    int count(int x) {
        return size[find(x)]; //计数
    }

    vector<int> p;  //记录集合中的元素，下标表示指针
    vector<int> size; //统计集合数
};

class Solution {
public:
    bool has_intersection(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 n = PeoplePosition.size();
        DSU dsu(n);
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (has_intersection(PeoplePosition[i], PeoplePosition[j]))
                    dsu._union(i, j); //合并区间
        return dsu.count(Personid); //包含下标Personid的集合由多少个区间组成
    }
};

复杂度分析：

时间复杂度： $O(n^2)$ ，两层遍历，每次都是 $O(n)$
空间复杂度： $O(n)$ ，并查集中构建了辅助数组，最大长度为 $n$