Problem 2. Consider the following problem faced by the manager of a small consulting company: the company has a list of potential jobs where every job has a deadline and associated profit if the job is finished before the deadline. The manager needs to decide which jobs to take, and when to schedule them, so as to maximize the total profit. We will assume that the deadline is given as a positive integer, where today is day 1, tomorrow is day 2, etc. and that each job takes exactly one day of work to complete. A job that is scheduled to be done on the same day as the deadline is considered to be on time. As an example, consider the jobs shown in the table below. Job | J1 J2 J3 J4J5 J6 | Deadline 214243 Profit 60 100 40 50 30 20 One way to schedule these jobs is to do job Jo on day 1, Jon day 2, J, on day 3, and Jz on day 4. This would result in a profit of 20+ 60 +30 + 40 = 150 dollars. Clearly, this is not the best solution, since other schedules can result in more profit. a) Although inefficient, this problem can be solved using a brute-force approach. Describe the brute-force approach in words, and show that it takes time S2(n!) A more efficient solution is as follows: Sort the jobs in decreasing order of profit. Working through the jobs in decreasing order of profit, schedule each job for the latest available day that is not after the deadline. If you cannot find an available day without missing the deadline, then don't schedule the current job. For example, if the jobs are as given above, then sorting the jobs in descending order of profit yields the following Job Deadline Profit J2J 1 2 100 60 JA 2 50 J3 4 40 J5 4 30 JA 3 20 Then we schedule J2 to be done on day 1. We schedule J to be done on day 2. We cannot schedule JA since the only available days in our schedule are after the deadline for J4, so we won't do job J4. Next, we schedule job J3 to be done on day 4 and J5 to be done on day 3, which is the only available day that is not after the deadline. There is no way to schedule Jo because days 1, 2, and 3 are already reserved. Thus, we will do the jobs in the following order, one per day: (J2, J1, J3, J5). The total profit of this schedule is 100+60 + 40 + 30 = 230 dollars. b) What is the asymptotic time complexity of this alternative approach? Does the sorting algorithm used affect the overall asymptotic complexity? Use big Oh notation with the smallest upper bound that you can come up with