# Problem 8.17 of Korte and Vygen

An airline wants to conduct a given set of scheduled flights with as few airplanes as possible. All available airplanes are of the same type. For each flight we know the departure time and the flight time. We also know, for any pair of flights i and j, how much time an airplane needs after finishing flight i until it can begin flight j (this time will depend in particular on where i ends and where j begins). Show how to compute efficiently a feasible schedule with as few airplanes as possible.

I feel a greedy approach combined with a priority queue here may be the way to go. Essentially, we:

• Sort all flights by their departure time. If two flights have the same departure time, sort them by their arrival time.

• Initialize a priority queue to store the arrival time of each flight. The priority queue will always return the smallest arrival time.

• For each flight in the sorted list, check if the departure time of the current flight is later than the arrival time of the earliest finished flight (which can be obtained from the priority queue). If it is, then the current flight can be assigned to the airplane that finished the earliest flight. In this case, update the arrival time of the earliest finished flight in the priority queue.

• If the departure time of the current flight is not later than the arrival time of the earliest finished flight, then the current flight needs a new airplane. In this case, add the arrival time of the current flight to the priority queue.

• The minimum number of airplanes needed is the size of the priority queue after all flights have been processed.

However I'm not sure whether this works or if there's a more ideal way for the problem. I would appreciate any advice.

Hints:

1. This exercise comes from a chapter on network flow.
2. Source and sink
3. Directed arcs
4. Split node $$i$$ and replace with arc from $$i$$ to $$i’$$ with lower bound $$1$$.
5. Minimize cost.

A few links that tie together the solution approaches discussed in your question and the two current answers:

• What would $i'$ mean here? Commented Feb 7 at 4:28
• The node $i’$ is the copy that results from splitting node $i$. Commented Feb 7 at 4:35

This could be seen as a graph coloring problem. The nodes are the possible flights. Draw an edge between two nodes if they are incompatible (how would they be incompatible?)

Then find an optimal coloring for the graph. What does the chromatic number give you?

• Welcome to ORSE. The graph is an interval graph, so an optimal coloring can be obtained efficiently. Commented Feb 7 at 18:03