Assume you work for an airline company and you need to assign aircraft to a set

Question

Assume you work for an airline company and you need to assign aircraft to a set of scheduled flights {Fi}, each departing and returning to the same hub airport. Assume that:
-The departure (dFi) and return (rRi) times of each flight Fi are fixed and given.
-Any flight Fi,can use anyone of the available aircraft in the infinite pool of aircraft A.
-No aircraft can fly two flights at the same time.
-Changing the assignment of an aircraft from a flight to another one can only take place at the hub airport.
Describe a greedy algorithm that minimizes the number of aircraft used (taken out of the hangars)
State and prove the time complexity of your algorithm

Explanation / Answer

Arrange the departure times in sorted order. The departure times will be in increasing order. Similarly arrange the return times in the incresing order.Then whenever we need to execute a filght, we just need to check if how many return times are above it and if we get a single entry staisfying that and the plane is avaliable, we should use that plane for the flight and if we don't satisfy the condition we should opt for a new plane. In this approach we just need to search a timing less than a given timing . Searching a number in a sorted entity, we can use binary search which will have complecxity of the order O(log n). For a given binary search tree, the searching steps will be equal to the height of a tree and height of the binary serach tree with n nodes is (log n).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.