Question 6
An airline has a flight schedule for October 16, 2010, which is shown in the following table.
| Flight no | From airport | To airport | Departure time | Arrival time | Flight time (hour) |
|---:|---|---|---|---|---:|
| 1 | A | B | 5:00 | 7:00 | 2 |
| 2 | A | C | 7:30 | 9:00 | 1.5 |
| 3 | C | A | 9:45 | 11:15 | 1.5 |
| 4 | C | B | 10:30 | 11:30 | 1 |
| 5 | A | C | 12:00 | 13:30 | 1.5 |
| 6 | B | C | 12:15 | 13:15 | 1 |
| 7 | B | A | 12:30 | 14:30 | 2 |
| 8 | C | A | 14:15 | 15:45 | 1.5 |
| 9 | A | D | 16:30 | 17:15 | 0.75 |
| 10 | D | A | 18:00 | 18:45 | 0.75 |
A sequence of non-overlapping flights leaving and returning to airport A in which the airport of arrival of a flight is the same as the airport of departure of the flight succeeding it is called a pairing. A pairing must satisfy the following labor regulations:
1. The maximum of total flying time for one day is 9 hours.
2. The maximum duty time for one day is 12 hours.
The duty time is a period of time which consists of flying time of the first flight, transit time 1, flying time of the second flight, transit time 2, flying time of the third flight, ..., flying time of the $n$th flight $(n\ge2)$.
The transit time between two non-overlapping consecutive flights $x$ and $y$ is the length of time between the arrival time of the flight $x$ and the departure time of the flight $y$.
An example of a pairing is given in the table below.
| Flight | Total flying time (hour) | Duty time (hour) |
|---|---|---|
| 2-3-5-8 | $1.5+1.5+1.5+1.5=6$ | $1.5+0.75$ (transit time 1) $+1.5+0.75$ (transit time 2) $+1.5+0.75$ (transit time 3) $+1.5=8.25$ |
The sequence of flights $1-6$ is not a pairing since it is not returning to airport A. The sequence of flights $6-8$ is not a pairing since it is not starting from airport A. The sequence of flights $1-7-9-10$ is also not a pairing since the duty time is more than 12 hours. Find all possible pairings on October 16, 2010.
| Flight no | From airport | To airport | Departure time | Arrival time | Flight time (hour) |
|---:|---|---|---|---|---:|
| 1 | A | B | 5:00 | 7:00 | 2 |
| 2 | A | C | 7:30 | 9:00 | 1.5 |
| 3 | C | A | 9:45 | 11:15 | 1.5 |
| 4 | C | B | 10:30 | 11:30 | 1 |
| 5 | A | C | 12:00 | 13:30 | 1.5 |
| 6 | B | C | 12:15 | 13:15 | 1 |
| 7 | B | A | 12:30 | 14:30 | 2 |
| 8 | C | A | 14:15 | 15:45 | 1.5 |
| 9 | A | D | 16:30 | 17:15 | 0.75 |
| 10 | D | A | 18:00 | 18:45 | 0.75 |
A sequence of non-overlapping flights leaving and returning to airport A in which the airport of arrival of a flight is the same as the airport of departure of the flight succeeding it is called a pairing. A pairing must satisfy the following labor regulations:
1. The maximum of total flying time for one day is 9 hours.
2. The maximum duty time for one day is 12 hours.
The duty time is a period of time which consists of flying time of the first flight, transit time 1, flying time of the second flight, transit time 2, flying time of the third flight, ..., flying time of the $n$th flight $(n\ge2)$.
The transit time between two non-overlapping consecutive flights $x$ and $y$ is the length of time between the arrival time of the flight $x$ and the departure time of the flight $y$.
An example of a pairing is given in the table below.
| Flight | Total flying time (hour) | Duty time (hour) |
|---|---|---|
| 2-3-5-8 | $1.5+1.5+1.5+1.5=6$ | $1.5+0.75$ (transit time 1) $+1.5+0.75$ (transit time 2) $+1.5+0.75$ (transit time 3) $+1.5=8.25$ |
The sequence of flights $1-6$ is not a pairing since it is not returning to airport A. The sequence of flights $6-8$ is not a pairing since it is not starting from airport A. The sequence of flights $1-7-9-10$ is also not a pairing since the duty time is more than 12 hours. Find all possible pairings on October 16, 2010.