Visa application reservation. Reservation is required for the time to submit Visa application document and interview. When the application is submitted, the reservation is removed from set of pending events Reserve request specifies the requested time, t, to get service from the Visa office. t will be added to the list of reservations if no other previous reservations are scheduled within k minutes both before and after t.

Given that the accepted reservation list is R = [R[0], R[1], R[2], , R[n-1]], where R[i] is the requested time of reservation i.

You are to write a Python program that takes R and a new request time, t, as input. Then, the program either add this new reservation to the list or reject, depending on whether the criteria for reservation is met.

a) Apply the insertion sort technique to keep the list R sorted all the time. Insert a new reservation into R only if it is at least k minutes away from both the reservations before and after t. b) If the length of R is n, what is the upperbound on the running time of the algorithm for proessing a new request in question a) above? c) As an alternative, if you store the reservation list R in a binary search tree, suggest the process of how t is to be determined whether it can be added into the list. d) Following the question c) above in which a binary search tree is utilized, what is the upperbound on the running time for processing a new request?

now X Example Imm21 26 29 36 + + + + time (mins) X X If k= 3, 24 is not OK (must be at least 3 minutes away from 26) 33 is OK 10 is invalid (already past)