题意理解

每个人的活动范围相当于一个闭区间，开始时有一个人被感染。由于闭区间之间可能存在交集，所以当一个闭区间被感染时，与它相交的闭区间也会被感染，这个过程是瞬间完成的。所以，假设被感染的闭区间集合为S，还未被感染的闭区间集合为E，找出E中与S相交的闭区间，它们被感染并加入到S，更新E；不断迭代该过程，直到S,E都不再更新。

方法一

使用并查集。并查集主要由两部分构成，find函数和Union函数。

我们把存在相交的闭区间视为同一类，若A和B相交，B和C相交，无论A和C是否相交，均视为同一类（即相交）。find函数用于寻找某个闭区间所属类的根的索引（该类中任意区间都可以视为根，一般用产生一个新类时的闭区间）。Union函数用于把两个相交的闭区间放到同一个类中去（赋予同样的根的位置）。

最后，我们只要找到第一个感染者对应区间所在的类，输出该类中包含了多少个闭区间。

具体代码如下：

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Personid int整型 Personid
     * @param PeoplePosition Point类vector PeoplePosition
     * @return int整型
     */
    vector<int> pre;//记录每个闭区间所在类的根的索引
    vector<int> count;//记录每个类中包含了几个闭区间
    int find(int x)
    { 
        int r=x;
        while (pre[r] != r)
            r=pre[r];
        int i=x, j;
        //路径压缩
        while(i != r)
        {
             j = pre[i]; 
             pre[i]= r ;
             i=j;
        }
        return r;
    }
    
    void Union(int x, int y)
    {
        int a =find(x);
        int b = find(y);
        if (a==b) return;
        pre[a] = b;
        count[b] += count[a];
    }
    
    
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        // write code here
        int len = PeoplePosition.size();
        for (int i=0;i<len;i++)
        {
            pre.push_back(i);
            count.push_back(1);
        }
        //双重循环判断每两个闭区间是否相交
        for (int i=0;i<len;i++)
        {
            for (int j=i+1;j<len;j++)
            {
                if (PeoplePosition[i].y<PeoplePosition[j].x
                   || PeoplePosition[j].y<PeoplePosition[i].x)
                    continue;
                Union(i,j);
            }
        }
        return count[find(Personid)];
    }
};

时间复杂度：$O\left(N^{2}logN\right)O(N^2logN)$O(N2logN)。一个双重循环，循环内Union调用find，find的时间复杂度为$O\left(N\right)O(N)$O(N)，但是这样还是会超时。

空间复杂度：$O\left(N\right)O(N)$O(N)。创建了数组pre和count。

方法二

最直接的想法就是：（1）找出所有E中与S里区间相交的闭区间，将其加入S；（2）更新S和E。不断重复以上两步操作，直到S,E不再变化。但是这样会导致时间复杂度过高，每次第一步需要双重循环，而且重复的次数也可能要N次。

尝试对数据进行预处理，按照闭区间的起点对闭区间进行排序。从左到右遍历区间，将相交的闭区间合并成一个更大的区间group[i]，维护一个最右值right，表示合并后区间的右端点，并且用count记录该合并区间中包含了几个原始闭区间。对于每个区间，考察其两个端点和right的关系。

1、左端点大于right，该区间不属于group[i]，那么之前的闭区间已经合并好了，作为一个新区间进行合并。

2、左端点小于等于right，且右端点大于等于right，则更新right，count加1。

3、右端点小于right，则count加1。

以上操作将原始闭区间按照是否相交进行了合并，最后有一个合并区间包含原始感染者，输出该合并区间对应的count即可。

示意图如下：

具体代码如下：

/**
 * struct Point {
 *	int x;
 *	int y;
 *	Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param Personid int整型 Personid
     * @param PeoplePosition Point类vector PeoplePosition
     * @return int整型
     */
    static bool cmp(Point p1, Point p2)
    {
        return p1.x<p2.x;
    }
    
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        // write code here
        int len = PeoplePosition.size();
        int count = 1, x = PeoplePosition[Personid].x, y = PeoplePosition[Personid].y;
        bool getIll = false;//记录当前遇到的区间是否被感染
        sort(PeoplePosition.begin(),PeoplePosition.end(),cmp);
        for (int i=0;i<len;i++)
        {
            if (PeoplePosition[i].x == x && PeoplePosition[i].y == y)
            {
                Personid = i;//找到第一个感染者对应的区间位置
            }
        }
        int left,right,ans;
        left = PeoplePosition[0].x;
        right = PeoplePosition[0].y;
        if (Personid==0) getIll = true;
        for (int i=1;i<len;i++)
        {
            //分3种情况讨论
            if (right<PeoplePosition[i].x)
            {
                if (getIll) break;
                count = 1;
                left = PeoplePosition[i].x;
                right = PeoplePosition[i].y;
            }
            else if (PeoplePosition[i].x<=right && right<=PeoplePosition[i].y)
            {
                right = PeoplePosition[i].y;
                count++;
            }
            else if (PeoplePosition[i].y<right) count++;
            if (Personid == i) getIll = true;
        }
        return count;
    }
};

时间复杂度：$O\left(NlogN\right)O(NlogN)$O(NlogN)。排序用到的时间最多，后面的遍历只是单重for循环。

空间复杂度：$O\left(1\right)O(1)$O(1)。没有开辟新的数组。