Given a set of weighted intervals, choose a set of non-overlapping intervals such that the total weight is maximal. You may think of the weight as the profit for doing the work in the given interval

A weighted interval x can be represented by a triple

x = (s, f, v),

where

s = start time of x, f = finish time of x, v = weight or profit of this job

The weighted intervals can be represented by the triples

(0,3,3) (1,4,2) (0,5,4) (3,6,1) (4,7,2) (3,9,5) (5,10,2) (8,10,1)

Write a program to compute a solution to the Weighted Interval Scheduling problem.

Your program must read in a set of weighted intervals. Each interval should be entered as 3 integers. The intervals must be given in a textfile and also be entered in increasing order of finish time. In the above case we would have

0 3 3 1 4 2 0 5 4 3 6 1 ...

The program must print out the value of the total weight or profit of the optimum solution and the indices of the jobs. The output must be in the following format (the output below does NOT have the correct result).

Optimum profit: 7

Usng Jobs: 2 5

The program MUST use recursion. You must also perform a run using the following sample data set:

Number of Jobs n = 4

Job Details {Start Time, Finish Time, Profit}

Job 1: {1, 2, 50}

Job 2: {3, 5, 20}

Job 3: {6, 19, 100}

Job 4: {2, 100, 200}