Suppose you work for a major airline and are given the job of writing the algorithm for processing upgrades into first class on various flights. Any frequent flyer can request an upgrade for his or her up-coming flight using this online system. Frequent flyers have different priorities, which are determined first by frequent flyer status (which can be, in order, silver, gold, platinum, and super) and then, if there are ties, by length of time in the waiting list. In addition, at any time prior to the flight, a frequent flyer can cancel his or her upgrade request (for instance, if he or she wants to take a different flight), using a confirmation code they got when he or she made his or her upgrade request. When it is time to determine upgrades for a flight that is about to depart, the gate agents inform the system of the number, k, of seats available in first class, and it needs to match those seats with the k highest-priority passengers on the waiting list.

Design a system that can process upgrade requests and cancellations in O(log n) time and can determine the k highest-priority flyers on the waiting list in O(k log n) time, where n is the number of frequent flyers on the waiting list.

1. Write a JAVA program that interactively allows the user to choose one of the following options

$> PassengerList

1. Request upgrade

2. Cancel upgrade

3. Print upgrade list

Make a choice (1-3):

Choosing 1 or 2 should further ask for a passenger name and frequent flyer status.Take appropriate action (ie add or remove them from the list).

Choosing 3 should prompt user to enter a number for k (the number of available seats in first class) and prints the list of upgrade passengers

2. Explain (in README) the cost model and recurrence and prove that the algorithm operates in O(klogn).