Problem 3: Greedy (30 points) Every day during lunchtime, customers i=1,2,,n show up to get their sandwich from a cafe. The server knows all the customers and knows their orders, oi,,on. The server also knows, how much tip Ti the customer i will give. Some sandwiches are fast and straightforward to make, while some are complex and take a longer time to make. Let ti be the time it takes to make the sandwich for order oi. Assume the server can make the sandwiches in any order that they wish and that they make sandwiches back-to-back (without any breaks) until all orders are done. Based on the order that the server chooses to complete all orders, let Di be the time that the server finishes order i. (a) (20 points) Describe a greedy algorithm that helps the server to pick a schedule that minimizes the quantity: inTiDi. In other words, they want to serve the high-tippers the fastest, but they also wants to take into consideration the time it takes to make each sandwich. To get credit, your solution must be greedy. (Hint: think about a property that is true about an optimal solution.) (b) (10 points) Explain (you do not need to provide a formal proof) why your solution will give the correct