Please assist me with the following question. Work shown in detail would be grea
ID: 3824754 • Letter: P
Question
Please assist me with the following question. Work shown in detail would be greatly appreciated
You have n trucks. T_1, ..., T_n, sitting in a parking lot waiting to be loaded. For each truck, it costs you $0.10 per minute to keep it in the parking lot. The trucks have different sizes. For each truck T_i, you know the number of minutes t_i that it will take to load the truck. You can only load one truck at a time. Once you're finished loading a truck, it can immediately leave the parking lot, and you can immediately begin loading another truck. Describe an algorithm that determines the optimal order in which to load the trucks, so that you will incur the lowest parking fees possible. For example, if there are two trucks, with times t_1 = 4 and t_2 = 3, then loading T_1 first and T_2 second will incur parking fees of 4 * .10 + 7 * .10 = $1.10, since the first truck leaves after 4 minutes, and the second after 7 minutes. But if you loaded them in the opposite order, it would only cost you $1.00.Explanation / Answer
Solution:
In the above algorithm we are just sorting the order of time which a truck will take to load. and starting from the truck which will take lesser time, hence it will decrease the cost of parking the truck, which is going to be optimal.
The above algorithm will take O(n log n ) time. for sorting and O(n) time in loading the truck and calculating the sum of cost. So T(n)= O(n log n).
I hope this helps. Don't forget to give a thumbs up if you like this.