Two-Flight Crew Rosters

Maximum disjoint index pairs with a minimum value gap in a sorted array

MediumTwo PointersGreedySorted Arrays

An airline is building two-flight crew assignments from a departure schedule. The array departures contains departure times in nondecreasing order. Each array index represents a separate flight, even when several flights have the same departure time.

A crew assignment is a pair of indices [a, b] such that a < b and departures[b] - departures[a] >= min_rest. Each flight may appear in at most one assignment. Flights not included in an assignment are handled separately.

Find the maximum possible number of assignments, k, and return the following canonical roster:

  • Use the first k flights as the earlier flights.
  • Use the last k flights as the later flights.
  • Pair them in order: return [i, n - k + i] for each i from 0 through k - 1, where n is the number of flights.

For the maximum feasible k, this canonical roster is always valid. Return the pairs in increasing order of their first index. If no assignment is possible, return an empty list.

Examples

Example 1

Input: departures = [10,20,30,70,80,90], min_rest = 50
Output: [[0,3],[1,4],[2,5]]

Three assignments are possible. The canonical roster uses the first three flights and the last three flights, pairing them in order. Every resulting departure-time gap meets the required rest.

Example 2

Input: departures = [0,1,2,3,100], min_rest = 50
Output: [[0,4]]

Only one assignment is possible: any valid assignment must use the final flight as its later flight. The canonical rule selects the first flight as its earlier flight.

Example 3

Input: departures = [12,12,12,12,12], min_rest = 0
Output: [[0,3],[1,4]]

Equal departure times still represent separate flights. With zero required rest, two disjoint assignments can be made, leaving the middle flight unused.

Constraints

  • 0 <= departures.length <= 10000
  • 0 <= departures[i] <= 1000000000
  • departures is sorted in nondecreasing order.
  • 0 <= min_rest <= 1000000000

The intended solution takes O(n) time and O(1) auxiliary space, excluding the returned roster. Departure-time differences, rather than flight durations, determine eligibility.

Hints

Show hint 1

If k assignments are feasible, replacing their earlier flights with the first k flights and their later flights with the last k flights cannot make the ordered pairing harder.

Show hint 2

Keep one pointer in the first floor(n / 2) flights and another in the remaining flights. If their gap is too small, only advance the later-flight pointer.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you handle an unsorted departure list while returning original flight indices and making ties deterministic?
  • How would you test whether exactly k assignments are possible using constant extra space, without constructing a roster?

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