Intervals with costs and limited resources, dynamic programming

Question

I have been trying to solve the following problem. I have n intervals each with a cost.I want to choose a subset of the intervals that maximizes the cost but with the following constraint. Each interval when chosen uses one resource from a limited amount say k and when it finishes releases the resource to be used by another interval.

I have been thinking a dynamic programming approach. Where I sort with respect to endpoints first and use C[i,r,j] which is the optimal cost for i to n subproblem with r remaining resources and j is the first interval given a subset of intervals up to i-1 satisfying the limited resource constraint.

I have also found a TSP-like dynamic programming solution that uses powerset but the input is limited by the bitmask that implements the powerset of intervals and it has bad complexity.

I would like a hint on how to approach the problem.

• SilvioM: How the fact that your objects are intervals impact the solution? If it does not care it seems a knapsack problem (you have costs=values to maximize and resources=weights to keep under a certain treshold)
• SotirisD: At each point in time you can have up to k intervals active. So you can have in total more than k intervals chosen in the solution as long as you don't surpass the resources in a certain point in time. Say you have k cars to rent and deals from customers for certain intervals and with a certain cost and you have to choose which ones to accept.