Hi community, I came across below interview problems, I just wanna know if we can solve it using DFS. Thanks in advance!
Problem:
Given an origin airport, destination airport, and series of flights determine whether it is possible for a package at the origin to reach the destination. A flight is represented as departure airport, arrival airport, departure time, and arrival time. During the transportation, the time that the package leaves the airport needs to be greater than or equal to the time it arrives at the airport. Please determine whether it is possible for a package transfer from s to t. The package arrived at s at time 0.
- E.g. 1
- Origin: "NYC"
- Destination: "SFO"
- Flights: {{NYC -> LAX, Departure: 0, Arrival: 4}, {LAX -> SFO, Departure: 5, Arrival: 7}}
- Output: True
E.g 2
- Origin: "NYC" Destination: "SFO"
- Flights:{{NYC -> LAX, Departure: 0, Arrival: 4}, {LAX -> SFO, Departure: 3, Arrival: 5}}
- Output: False
I don't know if the constraints allow it, but my first thought was: build a new graph where each vertex is a pair u = (city, time) and the edges are directional and connect u and v where u.city = origin, u.time = departure, v.city = destination, v.time = arrival. Also u is connected to v if u.city = v.city and v.time = u.time + 1 (that is, you can just wait at the current location). Then do a dfs / bfs and see if you ever reach a vertex of the form (target, any_time >= 0)
Not sure about dfs but I think you can solve with dp, initially set dist of origin to 0 and all others to infinity then process flights in increasing order of departure time. For each flight, if the dist to origin is less than or equal to its departure time then set the dist of its destination to its arrival time (if smaller than existing value)
DFS cannot solve it because you essentially have weighted edges.
Just run any shortest-path algorithm (e.g. Dijkstra) to find the earliest you can arrive on any airport and ignore flights that are impossible to catch.