# Question: for each 1 job is...

###### Question details

For each 1 ≤ 𝑖 ≤ 𝑛 job 𝑗𝑖 is given by two numbers 𝑑𝑖 and 𝑝𝑖, where 𝑑𝑖 is the deadline and 𝑝𝑖 is the penalty. The length of each job is equal to 1 minute and once the job starts it cannot be stopped until completed. We want to schedule all jobs, but only one job can run at any given time. If job i does not complete on or before its deadline, we will pay its penalty 𝑝𝑖. Design a greedy algorithm to find a schedule such that all jobs are completed and the sum of all penalties is minimized. What is the running time of your algorithm?