题解 | #病毒扩散#

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

方法一：贪心解法

求解思路
对于求解本题，我们要找多少人感染上病毒，就是找每个人活动范围的交集，然后取交点最多的那个区间并输出结果。对于如果求解交集，我们可以用贪心的思想去寻找，按照左端点从大到小排序，维护右端点的最大值，这样我们就可以知道每一个区间中有多少交点，这样即可得到本问题的答案。

图片说明

解题代码

class Solution {
public:
    int CatchVirus(int Personid, vector<Point>& PeoplePosition)
    {
        int n = PeoplePosition.size(); // 存储人的数量
        Point inf = PeoplePosition[Personid]; // 声明每个人的位置
        sort(PeoplePosition.begin(), PeoplePosition.end(), [](Point& a, Point& b) {return a.x < b.x; }); // 贪心排序
        int r = -1, count = 0, fg = 0;
        for (int i = 0; i < n; i++)
        {
            if (PeoplePosition[i].x > r) // 如果越界了，则直接跳过即可
            {
                if (fg == 1) break;
                count = 1;
                r = PeoplePosition[i].y;
            }
            else
                r = max(r, PeoplePosition[i].y), count++;
            if (PeoplePosition[i].x == inf.x&& PeoplePosition[i].y == inf.y) fg = 1;
        }
        return count; // 返回结果
    }
};

复杂度分析
时间复杂度：使用贪心思想求解，因此时间复杂度为 $O(NlogN)$
空间复杂度：没有使用额外的内存地址空间,因此空间复杂度为 $O(1)$

方法二：线段树的思想求解

求解思路
对于本题我们也可以用线段树来覆盖区间，但是需要注意的是，我们要以0.5作为线段树的最小刻度，这样可以同时保证线段树和题目的区间都为递增区间。最后我们对线段树的每一部分进行统计，将范围最广的线段树作为本题所要求解的答案即可。

图片说明

解题代码

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const int N=3000010;
bool add[N<<2],a[N];
int b[N],l[N/6],r[N/6];
vector<int> v;
void myedit(int L,int R,int l,int r,int rt)
{   //线段树区间覆盖
    if (L<=l&&r<=R) {add[rt]=1;return;}
    int m=(l+r)>>1;
    if(L<=m) myedit(L,R,lson); // 使用线段树对每个区间进行操作
    if(m<R) myedit(L,R,rson);
}
void myget(int l,int r,int rt)
{   //获取区间覆盖后的结果
    if (l==r) {a[l]=add[rt];return;}
    if(add[rt]) add[rt<<1|1]=add[rt<<1]=add[rt];
    int m=(l+r)>>1;
    myget(lson),myget(rson); // 进行递归即可
}
class Solution {
public:
    int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
        int n=PeoplePosition.size(); // 存储人的数量
        for(int i=0;i<n;i++)
        {   //以0.5作为最小单位进行离散化，因为double不好处理所以这里我们*2效果一样
            v.push_back(PeoplePosition[i].x*2);
            v.push_back(PeoplePosition[i].x*2+1);
            v.push_back(PeoplePosition[i].x*2-1);
            v.push_back(PeoplePosition[i].y*2);
            v.push_back(PeoplePosition[i].y*2-1);
            v.push_back(PeoplePosition[i].y*2+1);
        }
        sort(v.begin(),v.end()); // 快排
        v.erase(unique(v.begin(),v.end()),v.end());
        int sz=v.size();
        for(int i=0;i<n;i++)
        {
            l[i]=lower_bound(v.begin(),v.end(),PeoplePosition[i].x*2)-v.begin()+1; // 获取离散化后的L
            r[i]=lower_bound(v.begin(),v.end(),PeoplePosition[i].y*2)-v.begin()+1; // 获取离散化后的R
            myedit(l[i],r[i],1,sz,1); // 区间覆盖
        }
        myget(1,sz,1); // 获取区间覆盖后的答案
        int L=lower_bound(v.begin(),v.end(),PeoplePosition[Personid].x*2)-v.begin()+1;
        int R=lower_bound(v.begin(),v.end(),PeoplePosition[Personid].y*2)-v.begin()+1;
        for(int i=L;i<=R;i++) b[i]=1;
        for(;L&&a[L];L--) b[L]=1; // Personid线段最左能到达哪里
        for(;R<=sz&&a[R];R++) b[R]=1; // Personid线段最右能到达哪里
        for(int i=1;i<=sz;i++) b[i]+=b[i-1]; // 求前缀和
        int myans=0;
        for(int i=0;i<n;i++) 
            if(b[r[i]]-b[l[i]-1]>0) myans++; // 如果Personid能到达所在线段
        return myans; // 返回结果即可
    }
};

复杂度分析
时间复杂度：使用线段树，因此时间复杂度为 $O(NlogN)$
空间复杂度：使用辅助数组add[n]，因此空间复杂度为 $O(N)$