描述

牛牛刚刚得知牛牛所在的街道上有一个人得了新型冠状病毒！！！由于新型冠状病毒传染力很强，所以，只要在被传染的人的活动范围内活动都有可能被感染！现根据大数据可以得知，初始患病人在整个街道人群中的序号Pid和每个人在街道上的活动区域Pos。因为情况紧急，所以牛牛想请你帮忙快速计算下究竟最坏情况下会有多少人感染上冠状病毒？


示例1

输入： 
1,[(1,2),(2,3)]
复制
返回值： 
2
复制
说明： 
最坏情况下两个人都被感染

示例2

输入： 
1,[(1,2),(3,4)]
复制
返回值： 
1
复制
说明： 
				

					最坏情况下只有一个人被感染

备注： 

		

			人的编号从0开始
		


		

			
			

				第ii个人的活动范围为[Pos[i].x,Pos[i].y];
			


			

				0 \leq Pid0≤Pid<Pos.size \leq 5*10^{5}Pos.size≤5∗105
			

1\leq Pos[i].x \leq Pos[i].y \leq 10^{9}1≤Pos[i].x≤Pos[i].y≤109
解题思路
1、并查集
病毒传播，本质上是看与患者有交集的人数，可以将这种交集概括为连通性，使用并查集可以实现。
但即使简化成时间复杂度为O(1)的并查集，依旧会超时。因为要遍历完数组用双层for循环的时间复杂度是O(n*n) 
/**
 * struct Point {
 *  int x;
 *  int y;
 *  Point(int xx, int yy) : x(xx), y(yy) {}
 * };
 */
class Solution {
  public:
    vector<int> p;
    vector<int> cnt;
    int find(int x) {
        while (x != p[x]) {
            p[x] = p[p[x]];
            x = p[x];
        }
        return x;
    }

    void Union(int x, int y) {
        int rootx = find(x);
        int rooty = find(y);
        if (rootx == rooty) {
            return;
        }
        if (cnt[rootx] > cnt[rooty]) {
            p[rooty] = rootx;
            cnt[rootx] += cnt[rooty];
        } else {
            p[rootx] = rooty;
            cnt[rooty] += cnt[rootx];
        }
        
    }

    bool check(Point& a, Point& b) {
        if (a.x > b.y || a.y < b.x) {
            return false;
        }
        return true;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param Personid int整型 Personid
     * @param PeoplePosition Point类vector PeoplePosition
     * @return int整型
     */
     //两层for循环会导致超时
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        int n = PeoplePosition.size();
        p.resize(n+1, 0);
        cnt.resize(n+1, 1);
        for (int i = 0; i <= n ; i++) {
            p[i] = i;
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (check(PeoplePosition[i], PeoplePosition[j])) {
                    Union(i, j);
                }
            }
        }
        return cnt[find(Personid)];
    }
2、贪心算法
1）本题本质上是求一些线段的交集，可以先使用结构体排序的方法，根据每一段的x点进行升序排列
sort(PeoplePosition.begin(), PeoplePosition.end(), [](Point a, Point b){ return a.x < b.x;});
2）在小于患者所在区域的线段上计算有交集的区域个数，将区域个数累加，直到遇到一个没有交集的区域，之前累积的结果要复位为1；
3）在遍历到患者所在区域后，之前累加的交集就会变成与患者的交集，之后再遇到没有交集的区域，遍历就应该结束了；
4）如何确认是否是有交集的区域呢？因为x已经按照从小到大的顺序排列了，因此只要比较y的值即可，
每次将之前的y的最大值记录到last，last与当前的x作比较即可知是否有交集。 

/**
 * 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整型
     */
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        int n = PeoplePosition.size();
        Point target = PeoplePosition[Personid];
        sort(PeoplePosition.begin(), PeoplePosition.end(), [](Point a, Point b){ return a.x < b.x;});
        int res = 0;
        int last = -1; // 记录排在前面的人的活动区间最大值
        int flag = 0;
        for (int i = 0; i < n; i++) {
           if (PeoplePosition[i].x > last) { //当前人的活动区间最小值比last大，说明没有交集
               if (flag == 1) break; // 遍历到比已知患者远且无交集的区域，遍历结束
               res = 1; //只有已知的一个患者被感染
               last = PeoplePosition[i].y;
           } else {
               res++;
               last = max(last,PeoplePosition[i].y);
           }
           if (PeoplePosition[i].x == target.x && PeoplePosition[i].y == target.y) {
               flag = 1;
           }
        }
        return res;
    }
};