Problem Description
LAX is the world’s fifth-busiest airport. It is therefore impossible to manually coordinate all of
the planes that are trying to land, make sure there is an open gate for each plane upon landing,
and again coordinate the planes trying to take off again. LAX’s air traffic controllers are asking
for the USC CS department to design a program to help them do this job.
The problem starts with
N airplanes flying over LAX, waiting to land, unload passengers, board
new passengers, and take off again. Each plane has only limited fuel remaining, allowing it to
stay in the air for at most
R minutes. A plane must begin its landing procedure before its fuel
runs out. The plane will arrive at a boarding gate
M minutes after starting its landing procedure.
It will then take
S minutes to unload passengers, refuel, board new passengers, etc. before it is
ready to take off again. If the plane spends more than
C minutes at the gate, the waiting
passengers will complain, which must be avoided at all cost. Once the plane leaves the gate, it
will take
O minutes for it to finally take off and for the inflight beverage service to begin.
Unfortunately, LAX does not have enough runways or boarding gates to allow all of the
airplanes to land, board, and take off whenever they want. Due to the crowded airspace and
the limited number of runways, there can be at most
L planes landing and at most T planes
taking off at the same time. Also, there are only
G boarding gates, and each gate can
accommodate only one plane at a time.
The problem facing the air traffic controllers is to assign each plane in the air a time when it
should begin its landing procedure and a time when it should begin its takeoff procedure. Each
plane must have enough fuel to stay in the air until its assigned landing time, a gate to stay at
before its time to take off again, and an early enough take off time so that its waiting
passengers do not complain.
Input Format
The input file name is “input.txt”.
<AIRPORT INFORMATION>:
contains 3 integers, L G T, separated by spaces. The first is the
maximum number of planes that can be landing at the same time. The second is the number of