Himanshi has overloaded on classes this semester to the point where it’s Friday and she realizes that she has homework assignments for all her courses due at different times that same day. Let there be n courses in total, and denote each homework assignment as hi (1 ≤ i ≤ n). Each homework assignment has a deadline di and late penalty pi associated with it. Assume that it takes Himanshi 1 hour for completing each homework assignment, and she can only work on one homework at any given time. If she does not finish homework hi before deadline di then she pays a penalty of pi in that course (no matter when she finishes it past the deadline). Required:
a. Design a greedy algorithm to help Himanshi schedule her homework assignments in a way that minimizes the sum of penalties and analyze the runtime of your algorithm. You can assume the time starts at 0 hours and goes up to n hours, where each time interval is of length 1 hour. Each deadline 1 ≤ di ≤ n and di is an integer. Your algorithm must output a list of n scheduled homework assignments. Example: Let n = 5, and list of homeworks represented as (di , pi) be [(2, 10),(1, 500),(2, 10),(4, 20),(5, 20)] , then one possible optimal solution is h2, h3, h1, h4, h5 which gives a total penalty of 10.

b. Prove the correctness of your algorithm.