解题思路:
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()