05 August 2008
给一个整数 n，表示有 n 个人，编号从 0 到 n - 1。还给你一个 0 索引的 2D 整数数组 meeting，其中 meeting[i] = [xi, yi, timei] 表示个人 xi 和 person我在timei开会。一个人可以同时参加多个会议。最后，给一个整数 firstPerson。
个人 0 有一个秘密，并且最初在时间 0 与一个人 firstPerson 共享该秘密。然后，每次与拥有该秘密的人开会时都会共享该秘密。更正式地说，对于每次会议，如果某个人 xi 在时间 i 有秘密，那么他们将与人 yi 分享秘密，反之亦然。
秘密立即共享。也就是说，一个人可能会收到秘密并在同一时间范围内与其他会议中的人分享。
在所有会议举行后，返回所有知道秘密的人的名单。您可以按任何顺序返回答案。
PriorityQueue
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
Map<Integer, List<int[]>> child = new HashMap<>();
for (int i = 0; i < n; i++) {
child.put(i, new ArrayList<>());
}
for (int[] meeting : meetings) {
child.get(meeting[0]).add(new int[]{meeting[1], meeting[2]});
child.get(meeting[1]).add(new int[]{meeting[0], meeting[2]});
}
PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
Set<Integer> visited = new HashSet<>();
visited.add(0);
visited.add(firstPerson);
for (int[] item : child.get(firstPerson)) {
queue.add(item);
}
for (int[] item : child.get(0)) {
queue.add(item);
}
List<Integer> result = new ArrayList<>();
result.add(0);
result.add(firstPerson);
int least_time = 0;
while (!queue.isEmpty()) {
int[] cur = queue.poll();
if (least_time <= cur[1]) {
least_time = cur[1];
if (!visited.contains(cur[0])) {
visited.add(cur[0]);
result.add(cur[0]);
for (int[] item : child.get(cur[0])) {
queue.add(item);
}
}
}
}
return result;
}
}