病毒扩散

 int mycmp(const void *a, const void *b)
 {
     return ((*(struct Point *)a).x - (*(struct Point *)b).x);
 }


int CatchVirus(int Personid, struct Point* PeoplePosition, int PeoplePositionLen ) {
    struct Point target = PeoplePosition[Personid];
    int flag = 0;
    int num = 0;
    int r = -1;
    
    qsort(PeoplePosition, PeoplePositionLen, sizeof(PeoplePosition[0]), mycmp);
    
    for (int i = 0; i < PeoplePositionLen; i++) {
        //printf("%d x=%d y=%d\n", i, PeoplePosition[i].x, PeoplePosition[i].y);
        if (PeoplePosition[i].x > r) {
            if (flag == 1) break;
            r = PeoplePosition[i].y;
            num = 0;
        }
        
        r = fmax(r, PeoplePosition[i].y);
        num++;
        
        if (PeoplePosition[i].x == target.x && PeoplePosition[i].y == target.y) {
            flag = 1;
        }
    }

    return num;
}

#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;
  }
};