Frontend School

Optimal Travel Window

DSA
hard

Optimal Travel Window

Hard
Sliding Window
Hash Map
Arrays

Overview

Makemytrip frequently optimizes travel packages to provide the best value to its users. Imagine a scenario where a user wants to explore a specific number of unique cities within a given total travel time budget, by chaining contiguous flight segments. This problem challenges you to identify the most cost-effective way to achieve this goal from a predefined sequence of available flight segments.

What you need to do / Task

  1. Implement a function findOptimalTravelWindow that takes a list of FlightSegment objects, a minimum required number of k unique cities, and a maxTotalDuration.
  2. Identify a contiguous sub-sequence of FlightSegments (a "travel window") that satisfies the following conditions:
    • The total number of unique cities (either as a source or destination) within the window is at least k.
    • The sum of duration for all segments in the window does not exceed maxTotalDuration.
  3. Among all such valid travel windows, determine and return the minimum possible total cost.
  4. If no such travel window exists that meets both criteria, return -1.

Input & output

  • Input:
    • segments: An array of FlightSegment objects. Each object has source: string, destination: string, cost: number, duration: number.
    • k: A non-negative integer representing the minimum required number of unique cities.
    • maxTotalDuration: A non-negative integer representing the maximum allowed total duration for the window.
  • Output:
    • A number representing the minimum total cost of a valid travel window, or -1 if no such window exists.

Clarifications

  • A city is considered "unique" if it appears as either a source or destination in any segment within the current window.
  • If a city appears multiple times within the window (e.g., as a source in one segment and destination in another, or multiple times as source/destination), it still counts as one unique city.
  • The segments in the input array are already ordered chronologically and represent potential contiguous connections.

Examples

1

Example 1

Input:

segments = [{source: "A", dest: "B", cost: 100, duration: 2}, {source: "B", dest: "C", cost: 50, duration: 1}, {source: "C", dest: "D", cost: 200, duration: 3}, {source: "D", dest: "E", cost: 70, duration: 1}], k = 3, maxTotalDuration = 5

Output:

150

Note:

Consider the window [A-B, B-C]: Cities {A,B,C} (3 unique), total duration = 3, total cost = 150. This is a valid window. Other valid windows like [B-C, C-D] (cost 250) or [C-D, D-E] (cost 270) have higher costs. The minimum cost is 150.

2

Example 2

Input:

segments = [{source: "X", dest: "Y", cost: 10, duration: 10}, {source: "Y", dest: "Z", cost: 20, duration: 20}], k = 4, maxTotalDuration = 100

Output:

-1

Note:

The maximum number of unique cities achievable is 3 ({X,Y,Z}) by taking all segments. Since k = 4 is required, no valid window can be formed.

3

Example 3

Input:

segments = [{source: "P", dest: "Q", cost: 10, duration: 1}, {source: "Q", dest: "R", cost: 20, duration: 2}, {source: "R", dest: "S", cost: 30, duration: 10}, {source: "S", dest: "T", cost: 40, duration: 1}], k = 3, maxTotalDuration = 3

Output:

30

Note:

The window [P-Q, Q-R] has cities {P,Q,R} (3 unique), duration = 1+2 = 3, and cost = 10+20 = 30. This is valid. The window [Q-R, R-S] would have duration 2+10 = 12, exceeding maxTotalDuration = 3, so it's invalid. Similarly for [R-S, S-T]. Thus, 30 is the minimum cost.

Constraints

Constraints & assumptions

  • 1 <= segments.length <= 10^5
  • 0 <= k <= 2 * segments.length (since each segment has 2 cities, max unique cities is 2 * segments.length)
  • 0 <= maxTotalDuration <= 10^9
  • 1 <= segment.cost <= 10^4
  • 1 <= segment.duration <= 10^3
  • City names are strings, 1 <= city.length <= 20, consisting of English letters.
  • All costs and durations are non-negative integers.

What interviewers evaluate

  • Correct application of the sliding window technique for variable-size windows.
  • Efficient tracking of unique cities within the window using appropriate data structures (e.g., hash map for frequency counts).
  • Handling of edge cases, including empty input, no valid windows, and windows with single segments.
  • Time and space complexity optimization for large inputs, aiming for O(N) time and O(C) space where C is the number of unique cities.

Loading editor...