One Express Turnaround
Maximum interval weight with required gaps and one reduced gap allowed
A flight operator has one aircraft available for a collection of round-trip flights. Every flight leaves and returns to the same base.
Flight i departs at departures[i], returns at arrivals[i], and earns credits[i] credits if operated. A flight must be operated in full, and each flight can be selected at most once. The input flights are not necessarily in chronological order.
Normally, the aircraft needs at least normal_gap time units between returning from one selected flight and departing on the next. Once during the entire schedule, an express ground crew may reduce that required gap to express_gap time units. The express service is optional and applies only between two consecutive selected flights. There is no preparation requirement before the first selected flight or after the last one.
More precisely, if a selected flight returns at time a and the next selected flight departs at time d, their gap is d - a. Every such gap must be at least normal_gap, except that at most one may instead be at least express_gap. Equality is allowed.
Return the maximum total credits obtainable. You may select no flights, earning zero credits.
Examples
Example 1
Input: departures = [0,4,9], arrivals = [3,6,11], credits = [5,7,6], normal_gap = 3, express_gap = 1 Output: 18
The first two flights have a gap of one time unit, so selecting both requires the express service. The gap from the second flight to the third meets the normal requirement, allowing all three flights in one schedule.
Example 2
Input: departures = [0,3,6,0], arrivals = [2,5,8,8], credits = [6,6,6,15], normal_gap = 2, express_gap = 1 Output: 15
The first three flights each require an express turnaround to connect to the next one. Only one such turnaround is available. The fourth flight offers a competing schedule that spans the same operating period.
Example 3
Input: departures = [8,0,4,12], arrivals = [10,2,6,14], credits = [8,3,-5,7], normal_gap = 3, express_gap = 2 Output: 18
The flights are listed out of chronological order. Some have negative credit values, so operating every compatible flight is not necessarily beneficial.
Constraints
- 0 <= len(departures) <= 5000
- departures, arrivals, and credits have equal lengths.
- 0 <= departures[i] < arrivals[i] <= 10^9
- -10^6 <= credits[i] <= 10^6
- 0 <= express_gap <= normal_gap <= 10^9
The intended complexity is O(n log n) time and O(n) additional space. Credits may be negative, and the empty schedule is always valid.
Hints
Show hint 1Hint 1
Sort flights by return time. For any flight, compatible earlier flights form a prefix of this ordering.
Show hint 2Hint 2
Track the best total for each prefix both without express service and with at most one express service. Find the normal and express predecessor prefixes with binary search.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you extend the algorithm if express service could be used at most k times?
- How would you reconstruct a selected schedule, breaking ties by preferring fewer flights?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem