Optimal Flight Connection
At Ixigo, providing the best travel options to our users is paramount. We want to enhance our flight search engine to recommend not just the cheapest or fastest routes, but also those that balance convenience and overall journey time. This problem focuses on finding an optimal flight path based on a specific set of criteria that prioritizes minimal layovers and efficient total travel.
Implement the findOptimalFlightPath function that takes a list of available flights, a starting city, a destination city, and a maximum allowed total travel duration. Your function should return the 'best' flight path according to the following optimization rules:
Your solution must also respect the maxTotalDuration constraint for any valid path. If no such path exists, return a specific indicator.
Input:
flights: An array of Flight objects. Each Flight object has the following structure:
interface Flight {
source: string;
destination: string;
departureTime: number; // Unix timestamp
arrivalTime: number; // Unix timestamp
}
startCity: A string representing the city where the journey begins.endCity: A string representing the city where the journey ends.maxTotalDuration: A number representing the maximum allowed total travel time (in the same unit as departureTime/arrivalTime) from the first flight's departure to the last flight's arrival.Output:
[number, number] representing [minLayovers, minTotalDuration] for the optimal path found.maxTotalDuration), return [-1, -1].k flight segments has k-1 layovers.final_arrival_time - initial_departure_time for the entire journey.departureTime and arrivalTime are Unix timestamps (integers). You can assume they are valid and departureTime < arrivalTime for any single flight.departureTime is greater than or equal to the arrivalTime of your preceding flight at the same city.startCity is the same as endCity, the optimal path has 0 layovers and 0 total duration, provided maxTotalDuration >= 0.Examples
Example 1
Input:
flights = [ {source: "A", destination: "B", departureTime: 100, arrivalTime: 200}, {source: "B", destination: "C", departureTime: 250, arrivalTime: 350}, {source: "A", destination: "C", departureTime: 110, arrivalTime: 300} ], startCity = "A", endCity = "C", maxTotalDuration = 300
Output:
[0,190]
Note:
Two paths from A to C:
Example 2
Input:
flights = [ {source: "A", destination: "B", departureTime: 100, arrivalTime: 150}, {source: "B", destination: "C", departureTime: 160, arrivalTime: 200}, {source: "A", destination: "D", departureTime: 110, arrivalTime: 180}, {source: "D", destination: "C", departureTime: 190, arrivalTime: 220} ], startCity = "A", endCity = "C", maxTotalDuration = 100
Output:
[1,100]
Note:
Two paths from A to C, both with 1 layover:
Example 3
Input:
flights = [ {source: "A", destination: "B", departureTime: 100, arrivalTime: 150}, {source: "B", destination: "C", departureTime: 160, arrivalTime: 200}, {source: "C", destination: "D", departureTime: 210, arrivalTime: 250}, {source: "A", destination: "D", departureTime: 105, arrivalTime: 240} ], startCity = "A", endCity = "D", maxTotalDuration = 140
Output:
[0,135]
Note:
Two paths from A to D:
Constraints
N will be between 1 and 100.M will be between 0 and 1000.source, destination, startCity, endCity) are non-empty strings.departureTime, arrivalTime, and maxTotalDuration are positive integers, representing time in a consistent unit (e.g., minutes or seconds since epoch).startCity and endCity values are guaranteed to appear as source or destination in at least one flight, unless M=0.departureTime < arrivalTime for any given flight.Loading editor...