Consider the following problem for n jobs, each one of which takes exactly one minute to complete. At any time T = 1, 2, 3, , we can execute exactly one job. Each job i earns a profit of pi dollars if and only if it is executed no later than time d_i , where d_i is given as an input. Assume that d_i is an integer value. The problem is to schedule the jobs to maximize the profit.

Consider the following greedy strategy: For all the jobs with deadline at 1 minute, schedule the job with the maximum profit. Next, for all the jobs with deadline at 2 minutes or less, pick the job with maximum profit from the remaining unscheduled jobs. And so on. For example, consider n = 4, profits P = (50, 10, 15, 30) and deadlines D = (2, 1, 2, 1). The greedy strategy will yield the following solution: job 4 and job 1 to be scheduled for a total of profit of 80 dollars.

Give a counter example to establish that this greedy strategy does not always work.

If you can explain it in detail how we can give a counter example that shows that this greedy strategy doesn't work.