hw help please!!!

CSE 4310 - Worksheet 5 Dynamic Programming P.1 (20 pts) In the weighted interval scheduling problem, we are given n jobs, each of which has a start time, finish time, and weight. We say that two jobs are compatible if they do not overlap in time. We want to find the subset of compatible jobs with the maximum weight. In the figure below, the numbers in the rectangles represent the job weight. Figure 1 Weighted intervals Schedtaling: Jobs intervals and weights a. (15 pts.) Fill in the table below and calculate p[ ) and M[] columns, using the iterative algorithm we discussed in the class, memoizing the result in the M[] array. Compute p(1),p(2),,p(n) Iterative-Compute-Opt f M[0]=0 for j=1 to n 1 M[j]=max(wj+M[p(j)],M[j1]) b. (5 pts.) Once we are done executing the algorithm in (a), we have computed the total weight of the optimal schedule. However, we don't actually know which jobs to include. To extract that information, we will use a recursive algorithm Find-Solution, calling Find-Solution (n). Use this to fill in the last column of your table. Then list the jobs that provide maximum weight. Find-Solution(j) 1 if (j=0) return else if (Wj+M[P(j)]>M(j1]) Find-Solution (p(j)) e1se j is in the solution 1 Find-Solution (j-1)