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

• In fact, that obstacle can be ignored, if we use recursion and memorization, although it might slow down the computation. If we use iterative approach, that obstacle becomes critical. Apr 5 '20 at 23:55
• The running time of the iterative approach is $O(n^2)$. There is an obvious approach to reduce the computation time in general. To obtain $DP[i]$, we only need $DP[j]$'s such that $I_j$ is immediate before $I_i$, that is, there is no other interval between $I_j$ and $I_i$ that is disjoint with both of them. Apr 7 '20 at 0:18