CSL201: Assignment 5

In this assignment you shall implement a rudimentary flight trip planner. The input is the set of all flights between various cities. It is given as a file. Each line of the file contains "city1 city2 depart arrival flight-no." This means that there is a flight called "flight-no" (which can be a string) from city1 to city2 (again these can be arbitrary strings) which leaves city1 at time "depart" and arrives city2 at time "arrival". You can choose any convenient format for storing time.

Note that there could be multiple flights between two cities (at various times). For simplicity, assume that all flights depart after 5am and arrive before 5pm. Further assume that we would always want to travel for one day only (so no overnight staying at any of the cities).

Now given two cities "A" and "B", and a times "t1", "t2" you have to find a trip which leaves city "A" after time "t1" and arrives at city "B" before time "t2". Further the trip that you find should take as small time as possible. Note that the trip could involve multiple flights. But you must make sure that the arrival time of a flight in this trip is before the departure time of the next flight in the trip.

Your algorithm should be as efficient as possible.