首页 > 试题广场 > 病毒扩散
[编程题]病毒扩散
  • 热度指数:635 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛刚刚得知牛牛所在的街道上有一个人得了新型冠状病毒!!!由于新型冠状病毒传染力很强,所以,只要在被传染的人的活动范围内活动都有可能被感染!现根据大数据可以得知,初始患病人在整个街道人群中的序号Pid和每个人在街道上的活动区域Pos。因为情况紧急,所以牛牛想请你帮忙快速计算下究竟最坏情况下会有多少人感染上冠状病毒?


示例1

输入

1,[(1,2),(2,3)]

输出

2

说明

最坏情况下两个人都被感染
示例2

输入

1,[(1,2),(3,4)]

输出

1

说明

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

备注:
人的编号从0开始
个人的活动范围为[Pos[i].x,Pos[i].y];
<

#include <numeric>
class DSU {
public:
  DSU(int n) : p_(n), sizes_(n, 1) {
    iota(begin(p_), end(p_), 0);
  }
  
  int Find(int x) {
    if (p_[x] == x) return x;
    return p_[x] = Find(p_[x]);
  }
  
  void Union(const int u, const int v) {
    const int pu = Find(u);
    const int pv = Find(v);
    if (pu == pv) return;
    p_[pu] = pv;
    sizes_[pv] += sizes_[pu];
  }
  
  int size(int x) {
    return sizes_[Find(x)];
  }
  
private:
  vector<int> p_;
  vector<int> sizes_;
};

class Solution {
public:
  int CatchVirus(int Personid, vector<Point>& PeoplePosition) {
    const int n = PeoplePosition.size();
    DSU dsu(n);
    for (int i = 0; i < n; ++i)
      for (int j = i + 1; j < n; ++j)
         if (intersect(PeoplePosition[i], PeoplePosition[j]))
           dsu.Union(i, j);
    
    return dsu.size(Personid);
  }
  
private:
  // 判断两个intervals是否有交集
  bool intersect(const Point& a, const Point& b) {
    if (a.x < b.x) return b.x <= a.y;
    return a.x <= b.y;
  }
};

发表于 2021-08-04 13:51:53 回复(0)

问题信息

难度:
1条回答 770浏览

热门推荐

通过挑战的用户

查看代码