a bit of dp: SPOJ - RENT

Problem Statement:
SPOJ - RENT

Summary:
Given st[i] starting time, d[i] duration and p[i] price, find maximum total price possible from an optimal non-overlapping intervals.
\(N\leq 10000\) and \(st, d \leq 10^6\)

Solution:
This problem requires a DP technique coupled with Binary Search. We need to sort all intervals and start our construction from the last interval. Firstly, we mark dp[N] by 0. Then for each \(k = N-1, N-2 \ldots 0 \) we have the following relationship:
dp[k] = max(dp[k+1], dp[ index_of(st[k] + d[k]) ] + p[k])
Where index_of is a function which returns the index i of smallest st[i] such that st[i]  \(\geq \) st[k] + d[k] (i.e. the starting time of the closest non-overlapping interval). Implementation of index_of is naturally done by using a binary search. Hence overall we have a \(O(N\lg{N})\) running time algorithm.