Flight Delay Propagation
Learn this problem
IBMNEW GRADOAProblem statement
A network contains flightNodes flights, numbered from 1 through flightNodes. Dependencies are given by the parallel arrays flightFrom and flightTo.
For every index i, flight flightFrom[i] cannot depart until flight flightTo[i] has landed. Therefore, if flightTo[i] is delayed, flightFrom[i] also becomes delayed. That new delay propagates transitively to every flight that depends on it.
The array delayed lists the initially delayed flights. Return every flight that is initially delayed or becomes delayed through the dependency network. Include each flight exactly once and return the IDs in ascending order.
Function
propagateFlightDelays(flightNodes: int, flightFrom: int[], flightTo: int[], delayed: int[]) → int[]Examples
Example 1
flightNodes = 6flightFrom = [2,3,4,5]flightTo = [1,2,2,4]delayed = [1]return = [1,2,3,4,5]Flight 1 delays flight 2. Flight 2 then delays flights 3 and 4, and flight 4 delays flight 5. Flight 6 is unaffected.
Example 2
flightNodes = 5flightFrom = [1,2,3,4]flightTo = [2,3,4,5]delayed = [5]return = [1,2,3,4,5]Flight 5 delays flight 4, which delays 3, then 2, then 1. The direction follows from flightTo[i] to its dependent flightFrom[i].
Example 3
flightNodes = 6flightFrom = [2,2,3,5,6,6]flightTo = [1,1,2,4,5,5]delayed = [4,4]return = [4,5,6]The repeated initial ID and repeated dependency pairs have no extra effect. The delay spreads from flight 4 to 5 and then to 6.
Constraints
2 <= flightNodes <= 10^5.flightFrom.length = flightTo.length.- Every value in
flightFrom,flightTo, anddelayedis between1andflightNodes, inclusive. - Dependency pairs and initially delayed IDs may be repeated; repetitions do not duplicate an ID in the result.