Maximize rental income given a set of date intervals Suppose you have 1 room that you want to rent out. (AirBnb style) You want to maximize profits that you will get by renting it out. 

For example:
Given intervals: [[1, 10], [2, 5], [7, 20], [23, 30]] - you could rent it out [2, 5], [7, 20] and [23, 30]

Another example: ([[1, 2], [1, 11], [5, 8], [4, 33], [18, 72]]) = 66

Note: Start and end times of the interval are inclusive

I implemented a brute force solution to this problem. First I sort by start time, then I create all possible subsets and take the longest possible value. This works. But I want to do this using Dynamic programming.

This problem screams DP, but I am not able to figure out if this has an optimal substructure.

My recurrence relation: f(i, j) = f(i + 1, j) or f(i + nums[i], j) if nums[i].start &gt; f[i].end

Can someone help me figure out the thought behind the dp solution for the sub-problem?

Note: this problem is slightly different from job scheduling.
The most common subproblems where a particular subsequence should be selected are parametrized by the index of the last element selected. The classical, simple and brilliant example is Kadane's algorithm.

Let the given intervals are $I_1, I_2,\cdots, I_n$, where $I_j=[l_j, r_j]$.

The subproblem $DP[i]$, where $1\le i\le n$ is the maximum rent if the last interval rented is the $i$-th interval. The answer is $\max_iDP[i]$.

We could add an artificial base case, $DP[0]=0$, which says that the maximum rent is 0 if there is no interval rented.  

The recurrence relation is 
$$DP[i] = \text{Length}(I_i) + \max_{r_j\lt l_i} DP[j].$$

That is it, basically. There is a minor problem with the above recurrence relation, however. When we compute $DP[i]$, not all of $DP[j]$ with $r_j\lt l_i$ has been computed. I will leave it for you to resolve this minor obstacle.