Consider the Interval Scheduling Problem defined as follows: job compatible A job i is identified by its start times, and its finishing time Two jobs i and are compatible if they do not overlap: fissorf, S8 A set of jobs is compatible if all pairs of jobs are compatible An instance of the interval scheduling problem is a set of jobs. instance goal The goal is to schedule the largest set of compatible jobs. solution The optimal solution is the largest set of compatible jobs. If there are multiple sets with the same number of jobs, any of these sets is an optimal solution to the problem. The problem can be solved using the greedy approach seen in class. The idea is to sort the jobs according to some criterion and then choose to include or not include each one of the jobs. The selection part of the algorithm has linear running time. Consider the group of jobs consisting of the first selected job, together with all the jobs that are not compatible with it. Each time a new job is selected, we create a new such group consisting of the job itself, together with all the remaining jobs that are not com- patible with it. Since the groups are formed by pairwise incompatible jobs, at most one job from each such group can be selected. We argue that the solution found by the greedy algorithm is optimal because it selects exactly one job from each group. 3. Write a function that takes a set of such groups and returns all optimal solutions. You might need to use a brute force search, but try to optimize by discarding non-optimal solutions at an early stage