Weighted interval scheduling problem involves selecting an optimal set of non$-$overlapping requests such that the total weight is maximized.

Each request $j$ starts at $s_j$ and finishes at $f_j$ and has weight $v_j$

Two jobs are compatible if they do not overlap

Goal: find maximum weight subset of mutually compatible jobs.

An instance of the problem is given in the image below with jobs sorted according to finish times.

Use this information to answer the following questions.

Recall the greedy approach for solving interval scheduling problem in which we picked a subset of requests based on the earliest finish time. Apply that algorithm to the example above and output the subset of requests in the format $j-k-1-m-n-0.($Ensure that your output is ordered from the first to the last request to be carried out$)$

Answer:

The output is

And find p$($a$),$p$($b$),$p$($c$),$p$($d$),$p$($e$),$p$($f$),$p$($g$),$p$($h$)$