Optimal Travel Window
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.
findOptimalTravelWindow that takes a list of FlightSegment objects, a minimum required number of k unique cities, and a maxTotalDuration.FlightSegments (a "travel window") that satisfies the following conditions:
k.duration for all segments in the window does not exceed maxTotalDuration.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.number representing the minimum total cost of a valid travel window, or -1 if no such window exists.Examples
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.
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.
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
1 <= segments.length <= 10^50 <= k <= 2 * segments.length (since each segment has 2 cities, max unique cities is 2 * segments.length)0 <= maxTotalDuration <= 10^91 <= segment.cost <= 10^41 <= segment.duration <= 10^31 <= city.length <= 20, consisting of English letters.Loading editor...