Contact Tracing Through Timed Meetings
Hudson River Trading● HardINTERNPHONE SCREENProblem statement
There are n people, numbered 0 to n - 1. Person patientZero is infected at time 0.
Each entry [x, y, time] in meetings means persons x and y meet at time. If one of them is already infected at that time, the other one becomes infected at that time too.
Infection spreads instantly. A person infected at time t can infect others in meetings that also happen at time t, and those people can pass it on at time t as well. A person can be in several meetings at the same time. The order of the entries in meetings does not matter.
Return every person who is infected after all meetings, in increasing order. The answer always includes patientZero.
Function
findInfectedPeople(n: int, meetings: int[][], patientZero: int) → int[]Examples
Example 1
n = 5meetings = [[0,1,2],[1,2,5],[3,4,1]]patientZero = 0return = [0,1,2]Person 0 meets person 1 at time 2, so person 1 is infected at time 2. Person 1 then meets person 2 at time 5, which is later, so person 2 is infected too.
Persons 3 and 4 only meet each other, and neither is infected. The answer is [0, 1, 2].
Example 2
n = 4meetings = [[1,2,3],[0,1,5],[2,3,7]]patientZero = 0return = [0,1]Persons 1 and 2 meet at time 3, but person 1 is not infected until time 5. That earlier meeting does not spread anything, so person 2 stays healthy, and so does person 3, who meets only person 2.
The answer is [0, 1].
Example 3
n = 4meetings = [[2,3,4],[1,2,4],[0,1,4]]patientZero = 0return = [0,1,2,3]All three meetings happen at time 4. Person 0 infects person 1, person 1 infects person 2, and person 2 infects person 3, all at that same time.
The meetings are listed in the opposite order, but the order in the list does not matter. The answer is [0, 1, 2, 3].
Constraints
1 <= n <= 10^50 <= meetings.length <= 10^4meetings[i].length == 30 <= meetings[i][0], meetings[i][1] < nmeetings[i][0] != meetings[i][1]1 <= meetings[i][2] <= 10^90 <= patientZero < n