Consider a weighted version of the class scheduling problem seen during lecture, where different classes offer different numbers of credit hours (totally unrelated to the duration of the class lectures). The goal now is to choose a set of non-conflicting classes that give you the largest possible number of credit hours, given an array of start times, end times, and credit hours as input.

Formally, youre given three arrays S[1..n], F[1..n], and C[1..n] where S[i], F[i], and C[i] respectively give the start time, end time, and credit hours for course i. You must compute a credit-maximal conflict-free schedule defined as a subset X {1, 2, . . . , n} that maximizes P iX C[i] so that for each i, j X, either S[i] > F[ j] or S[ j] > F[i].

(a) Prove that the greedy algorithm given in classchoose the class that ends first and recursedoes not always return a credit-maximal conflict-free schedule.

GreedySchedule(S[1 .. n], F[1 .. n]):

sort F and permute S to match

count=1

X[count] =1

for i 2 to n

if S[i] > F[X[count]]

count=count + 1

X[count] =i

return X[1 .. count]

(b) Describe an algorithm to compute a credit-maximal conflict-free schedule in O(n 2 ) time.