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