## Tuesday, October 7, 2014

### 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.