We must schedule n jobs, each with a starting time si and a finishing time fi . We have a set of constraints of the following form, each about a pair of jobs: • job i finishes before job j starts • jobs i and j at least partially overlap. We want to assign each of the n starting and finishing times a distinct integer value from 1 to 2n, satisfying these constraints. Design an algorithm that produces such an assignment or reports that this is not possible. Argue that your algorithm is correct and analyze its running time.