Frontend School

Optimal Flight Connection

DSA
hard

Optimal Flight Connection

Hard
Graph
BFS
Shortest Path
Multi-objective
Time Dependent

Overview

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.

What you need to do / Task

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:

  1. Minimize Layovers: The primary objective is to find a path with the fewest possible layovers.
  2. Minimize Total Duration: Among all paths that satisfy the minimum layovers, choose the one with the earliest possible final arrival time (which translates to the minimum total travel duration from the initial departure to the final arrival).

Your solution must also respect the maxTotalDuration constraint for any valid path. If no such path exists, return a specific indicator.

Input & output

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:

  • A tuple [number, number] representing [minLayovers, minTotalDuration] for the optimal path found.
  • If no path satisfies all criteria (including maxTotalDuration), return [-1, -1].

Clarifications

  • Layovers: A layover occurs when you arrive at an intermediate city and then take another flight from that city. A direct flight (source to destination) has 0 layovers. A path with k flight segments has k-1 layovers.
  • Total Duration: This is calculated as final_arrival_time - initial_departure_time for the entire journey.
  • Time Stamps: departureTime and arrivalTime are Unix timestamps (integers). You can assume they are valid and departureTime < arrivalTime for any single flight.
  • Flight Connections: You can only take a subsequent flight if its departureTime is greater than or equal to the arrivalTime of your preceding flight at the same city.
  • Same Start/End City: If startCity is the same as endCity, the optimal path has 0 layovers and 0 total duration, provided maxTotalDuration >= 0.

Examples

1

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:

  1. A->B->C: 1 layover, total duration (350-100)=250. Valid (250 <= 300).
  2. A->C (direct): 0 layovers, total duration (300-110)=190. Valid (190 <= 300). The direct flight (Path 2) is optimal because it has fewer layovers (0 vs 1).
2

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:

  1. A->B->C: Departs A at 100, arrives C at 200. Total duration (200-100)=100. Valid (100 <= 100).
  2. A->D->C: Departs A at 110, arrives C at 220. Total duration (220-110)=110. Invalid (110 > 100). Path 1 is the only valid path, thus it is optimal.
3

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:

  1. A->B->C->D: 2 layovers, total duration (250-100)=150. Invalid (150 > 140).
  2. A->D (direct): 0 layovers, total duration (240-105)=135. Valid (135 <= 140). Path 2 is optimal as it's the only valid path, and has 0 layovers.

Constraints

Constraints & assumptions

  • The number of cities N will be between 1 and 100.
  • The number of flights M will be between 0 and 1000.
  • City names (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).
  • All startCity and endCity values are guaranteed to appear as source or destination in at least one flight, unless M=0.
  • It's guaranteed that departureTime < arrivalTime for any given flight.

What interviewers evaluate

  • Graph Traversal Proficiency: Demonstrates strong understanding and application of BFS for multi-objective shortest path problems.
  • State Management & Pruning: Effectively defines and manages the BFS queue state and uses memoization/pruning techniques to optimize search space and avoid redundant computations.
  • Correctness of Logic: Accurately handles time-dependent connections, calculates layovers and total duration, and prioritizes objectives (min layovers then min duration).
  • Edge Case Handling: Correctly addresses scenarios like no path found, direct flights, and same start/end cities.
  • Code Quality: Writes clean, readable, and well-structured code with appropriate data structures.

Loading editor...