Consider a modified version of the Activity Selection problem in which each activity

has a profit

$,$ in addition to a start time

and finish time

$.$ The goal is no longer to maximize the number of activities scheduled, but instead to maximize the total profit of the activities scheduled. That is$,$ we wish to choose a set

of mutually compatible activities such that

is maximized.

For example, given four jobs with the following start time, finish time, and profit values,