• For multi-stop itineraries, the arrival time of a flight at an intermediate stop must be less than the departing time of the next flight from that very same intermediate stop.
If these three constraints are satisfied for at least 1 passenger, then the capacity of the system is at least 1.
Datasets: We will be uploading a sample timetable which includes flight information for all three airlines. The first column is the source airport, the second column is the destination airport, the third column indicates the departure time, the fourth column indicates the arrival time and the fifth column indicates the capacity of the flight. The filename is “flights.txt”.
Hint: To accomplish this task, you might be thinking in similar lines with the process of “constructing a directed graph with all the cities represented as nodes and directed edges from a node A to B if there is a flight travelling from city A to city B”. However, such a graph only captures the spatial information (flights between cities) and not the temporal information (time of the flights). Thus, such an approach is incomplete and is not going to capture the entire picture. The graph you create should capture the temporal aspect of the task as well, in order to accurately capture the capacity of the NAS. For further simplification, you can round the flight times (departure and arrival) to the nearest hour.
1
