Exercise 3 (Greedy algorithms (30 points)) In this exercise, you will plan your homework with a greedy algorithm. The input is a list of homeworks defined by two arrays: deadlines and weights (the rela- tive importance of the homework towards your final grade). These arrays have the same size and they contain integers between 1 and 100. The index of each entry in the arrays represents a single home- work, for example, Homework 2 is defined as a homework with deadline deadlines [2] and weight weights[2]. Each homework takes exactly one hour to complete. Your task is to output a homeworkPlan: an array of length equal to the last deadline. Each entry in the array represents a one-hour timeslot, starting at 0 and ending at last deadline - 1'. For each time slot, homeworkPlan indicates the homework which you plan to do during that slot. You can only complete a single homework in one 1-hour slot. The homeworks are due at the beginning of a time slot, in other words if an assignment's deadline is x, then the last time slot when you can do it is x - 1. For example, if the homework is due at t=14, then you can complete it before or during the slot t=13. If your solution plans to do Homework 2 first, then you should have homeworkPlan[0] =2 in the output. Note that sometimes you will be given too much homework to complete in time, and that is okay. Your homework plan should maximize the sum of the weights of completed assignments. To organize your schedule, we give you a class HW_Sched.java, which defines an Assignment object, with a number (its index in the input array), a weight and a deadline. The input arrays are unsorted. As part of the greedy algorithm, the template we provide sorts the homeworks using Java's Collections.sort (). This sort function uses Java's compare () method, which takes two objects as input, compares them, and outputs the order they should appear in. The template will ask you to override this compare () method, which will alter the way in which Assignments will be ordered. You have to determine what comparison criterion you want to use. Given two assignments A1 and A2, the method should output: 0, if the two items are equivalent 1, if al should appear after a2 in the sorted list -1, if a2 should appear after al in the sorted list The compare method (called by Collections.sort ()) should be the only tool you use to re- organize lists and arrays in this problem. You will then implement the rest of the SelectAssignments () method. Exercise 3 (Greedy algorithms (30 points)) In this exercise, you will plan your homework with a greedy algorithm. The input is a list of homeworks defined by two arrays: deadlines and weights (the rela- tive importance of the homework towards your final grade). These arrays have the same size and they contain integers between 1 and 100. The index of each entry in the arrays represents a single home- work, for example, Homework 2 is defined as a homework with deadline deadlines [2] and weight weights[2]. Each homework takes exactly one hour to complete. Your task is to output a homeworkPlan: an array of length equal to the last deadline. Each entry in the array represents a one-hour timeslot, starting at 0 and ending at last deadline - 1'. For each time slot, homeworkPlan indicates the homework which you plan to do during that slot. You can only complete a single homework in one 1-hour slot. The homeworks are due at the beginning of a time slot, in other words if an assignment's deadline is x, then the last time slot when you can do it is x - 1. For example, if the homework is due at t=14, then you can complete it before or during the slot t=13. If your solution plans to do Homework 2 first, then you should have homeworkPlan[0] =2 in the output. Note that sometimes you will be given too much homework to complete in time, and that is okay. Your homework plan should maximize the sum of the weights of completed assignments. To organize your schedule, we give you a class HW_Sched.java, which defines an Assignment object, with a number (its index in the input array), a weight and a deadline. The input arrays are unsorted. As part of the greedy algorithm, the template we provide sorts the homeworks using Java's Collections.sort (). This sort function uses Java's compare () method, which takes two objects as input, compares them, and outputs the order they should appear in. The template will ask you to override this compare () method, which will alter the way in which Assignments will be ordered. You have to determine what comparison criterion you want to use. Given two assignments A1 and A2, the method should output: 0, if the two items are equivalent 1, if al should appear after a2 in the sorted list -1, if a2 should appear after al in the sorted list The compare method (called by Collections.sort ()) should be the only tool you use to re- organize lists and arrays in this problem. You will then implement the rest of the SelectAssignments () method