Homework 1: Interval Scheduling Consider the Interval Scheduling Problem defined as follows:

job compatible

instance goal solution

A job i is identified by its start time si and its finishing time fi.

Two jobs i and j are compatible if they do not overlap: fi sj or fj si

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. The goal is to schedule the largest set of compatible jobs.

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.

1. Writeafunctionthattakesaninstanceoftheproblemasinputandreturnsanoptimal solution. The selection process must take linear time:

Each element can be visited only a constant number of times Make sure to use appropriate data structures

2. Write a function that takes an instance of the problem as input and returns the afore- mentioned groups.

CSE 3500 page 1 of 2 Due: January 29, 2020

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.

• Write your code in Python.