SORRY what I wrote before isn't true

I don't know how to solve this problem faster than O(n^3)

cost[l][r] = sum of the costs of the agents whose intervals are completely included in [l,r]

d[j][i] = the maximum profit that you can make by "not buying" i-j houses out of the first i IF you buy the ith house

d[j][i] = max(d[j-1][i-1], max{d[j-1][k] + cost[k+1][i-1] | k < i-1})

the answer is cost[1][n]-d[k][n]

you can calculate d[][] in O(n^3), but I think that if you fix j, and take i < z:

let a be the index (a < i) for which you get the maximum value for d[j][i]

let b be the index (b < z) for which you get the maximum value for d[j][z]

then a < b? if this is true, then you can use divide et impera to calculate d[][] in O(n^2*logn)