Problem: In this programming assignment, you are tasked with the computation of the capacity of a simplified model of the National Airspace System (NAS). More specifically, we would like to compute the largest number of individuals that can travel between two large cities (in our case between Source: Los Angeles (LAX) and Destination: New York City (JFK)), in a 24-hour time period, using commercially available flights. Our 24-hour period will start at 6:00AM on one day and and end at 5:59 AM on the following day. Please use the data set that will be provided to you. The dataset is based on the flight schedule data published by the three largest airlines, American Airlines (AA), Delta Airlines (DL) and United Airlines (UA). Aside from these LAX and JFK, two our simplified model of NAS consists of the following airports (codes) as well – San Francisco (SFO), Phoenix (PHX), Seattle (SEA), Denver (DEN), Atlanta (ATL), Chicago (ORD), Boston (BOS) and Washington DC (IAD).

To compute the capacity of the NAS on that day, you should consider the following – (i) all direct (non-stop or single hop) flights between LAX and NYC, and (ii) multi-hop flights between the two cities, provided the stops are airports in the list above. If the stops are not airports mentioned in the list above, you can discard that itinerary. For instance, you can discard LAX to MIA to NYC, since Miami airport (MIA) is not in our model. You can include instances like (i) a non-stop flight from LAX to NYC, and (ii) a multi-hop flight which could take you from LAX to SFO to ATL to NYC. While considering the above two scenarios, please keep in the mind the following: only consider flights which depart LAX and arrive at NYC on the same day. For multi-hop flights, the flight departing LAX may not be the same flight which arrives at NYC. For instance, a passenger might fly from LAX to PHX on AA, PHX to ATL on DL and ATL to NYC on UA. For the computation of capacity of such a system, you must satisfy the following:

A passenger travel starts at LAX and ends at NYC.

For multi-hop itineraries, a passenger can take any of the 3 airlines to travel between two cities (one itinerary may involve all the three airlines).

For multi-hop itineraries, the arrival time of a flight at an intermediate airport must be earlier than the departing time of the next flight from that airport.

If these three constraints are satisfied for at least 1 passenger, then the capacity of the system is at least 1. Furthermore, you may assume that transit times in an intermediate airport can be 0 units of time. In other words, if a flight arrives at 11:00 and another flight departs at 11:00, then a passenger could take the departing flight provided the number of passengers on the flight do not exceed the capacity of the plane.

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 final column indicates the capacity of that flight. The filename is “flights.txt”.