1
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Apr 5, 2020 at 23:55
  • $\begingroup$ 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. $\endgroup$
    – John L.
    Commented Apr 7, 2020 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.