3. (15 pts.) You are given a set of n jobs, each runs in unit time. Job i has an integer-valued deadline time di 2 0 and a real-valued penalty pi0. Jobs may be scheduled to start at any non-negative integer time (0, 1, 2, etc), and only one job may run at a time. If job i completes at or before time di, then it incurs no penalty; otherwise, it is late and incurs penalty pi. The goal is to schedule all jobs so as to minimize the total penalty incurred. For each of the following greedy algorithms, either prove that it is correct, or give a simple counterexample with at most three jobs) to show that it fails. (a) Among unscheduled jobs that can be scheduled on time, consider the one whose deadline is the earliest (breaking ties with the highest penalty), and schedule it at the earliest available time. Repeat. (b) Among unscheduled jobs that can be scheduled on time, consider the one whose penalty is the highest (breaking ties with the earliest deadline), and schedule it at the earliest available time. Repeat. (c) Among unscheduled jobs that can be scheduled on time, consider the one whose penalty is the highest (breaking ties arbitrarily), and schedule it at the latest available time before its deadline. Repeat