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]
([[1, 2], [1, 11], [5, 8], [4, 33], [18, 72]]) =
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.