题解 | #病毒扩散#

解题思路：
1. 构建并查集
2. 判断区域是否重叠
3. 合并， 人数相加，新冠传递，坐标叠加
4. 返回新冠集合中的人数

class Pos:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def __repr__(self):
        return "x={},y={}".format(self.x, self.y)

class Node:
    def __init__(self, pos, has_COV19):
        self.pos = pos
        self.man = 1                # 人数
        self.has_COV19 = has_COV19  # 1表示得新冠，0表示未得新冠

    def union(self, node):
        self.pos.x = min(self.pos.x, node.pos.x)
        self.pos.y = max(self.pos.y, node.pos.y)
        self.has_COV19 += node.has_COV19
        self.man += node.man

    def find(self, node):
        range_1 = self.pos.y - self.pos.x
        range_2 = node.pos.y - node.pos.x
        range_3 = max(self.pos.y, node.pos.y) - min(self.pos.x, node.pos.x)
        return (range_1 + range_2) >= range_3

    def __repr__(self):
        return "pos={},man={},COV={}".format(self.pos, self.man, self.has_COV19)

class BCJSet:
    def __init__(self):
        self.bcj_set = list()

    def add(self, node:Node):
        """ 添加结点 """
        find_id = -1
        for i in range(len(self.bcj_set)):
            if node.find(self.bcj_set[i]):
                find_id = i
                self.bcj_set[i].union(node)
                break

        if find_id == -1: # 没有合并
            self.bcj_set.append(node)
        else:             # 有合并
            curr_node = self.bcj_set.pop(find_id)
            next_find_id = -1
            for i in range(len(self.bcj_set)):
                if curr_node.find(self.bcj_set[i]):
                    next_find_id = i
                    self.bcj_set[i].union(curr_node)
                    break
            if next_find_id == -1:
                self.bcj_set.append(curr_node)

    def get_rnt(self):
        for i in range(len(self.bcj_set)):
            if self.bcj_set[i].has_COV19 == 1:
                return self.bcj_set[i].man
        return 0

    def __repr__(self):
        return "&".join([str(tmp) for tmp in self.bcj_set])

class Solution:
    def CatchVirus(self , Personid , PeoplePosition ):
        # write code here
        bcj_set = BCJSet()
        for i in range(len(PeoplePosition)):
            bcj_set.add(Node(PeoplePosition[i], 1 if i == Personid else 0))
        # print(bcj_set)

        return bcj_set.get_rnt()