A new phone model is out! People have been waiting all morning for the store to...

Transcribed Image Text:

A new phone model is out! People have been waiting all morning for the store to open its doors. More specifically, there are n customers and their wait times (in minutes) are stored in array T[1..n]. Here, T[i] is the amount of time that a customer i has been waiting prior to the store opening its doors. Once the doors are opened your job is to assign customers to k different queues corresponding to k different cash registers. Each cashier takes 5 minutes per client. Thus, if client i is placed in a queue with j people in front of the client, the overall waiting time of client i is T[i] +5j. You wish to minimize the overall waiting time of the customer who waits the longest. Design an efficient greedy algorithm for this task. (a) (2 points) State what the inputs and outputs are for this problem. (b) (5 points) Describe your algorithm in plain English. (c) (5 points) Describe your algorithm in pseudocode. (d) (5 points) Formally prove correctness of your algorithm. (e) (3 points) State and justify the running time of your algorithm. Activate Windows Go to Settin A new phone model is out! People have been waiting all morning for the store to open its doors. More specifically, there are n customers and their wait times (in minutes) are stored in array T[1..n]. Here, T[i] is the amount of time that a customer i has been waiting prior to the store opening its doors. Once the doors are opened your job is to assign customers to k different queues corresponding to k different cash registers. Each cashier takes 5 minutes per client. Thus, if client i is placed in a queue with j people in front of the client, the overall waiting time of client i is T[i] +5j. You wish to minimize the overall waiting time of the customer who waits the longest. Design an efficient greedy algorithm for this task. (a) (2 points) State what the inputs and outputs are for this problem. (b) (5 points) Describe your algorithm in plain English. (c) (5 points) Describe your algorithm in pseudocode. (d) (5 points) Formally prove correctness of your algorithm. (e) (3 points) State and justify the running time of your algorithm. Activate Windows Go to Settin

Answer rating: 100% (QA)

a Inputs An array T1n representing the wait times in minutes of n customers before the store opens The number of cash registers k Outputs An assignmen... View the full answer