weighted interval scheduling solved by dynamic programming

Assume we have one resource and n requests to occupy this resource. The requests are given by start, finish times, and a value. The goal of this problem is to select a set of nonoverlapping requests for which the sum of the values is maximal over all possible nonoverlapping requests. Sorting the requests by finish time, we derive a recursive formula to compute the optimal selection. The recursive formula leads to a recursive algorithm with an exponential number of function calls. Memoization is a technique which stores the values of the solutions to the subproblems. Applying memoization we show that the weighted interval scheduling problem can be solved in a running time that is linear in the number of requests.