You are given a range [first, last], initially white. You need to paint it black. For this purpose you have a set of triples [(f, l, cost), ...] - where each triple means that you can paint range [f, l] for 'cost' coins (limitations: cost is floating point >= 0, f, l, first, last are integers).
Find the minimum cost needed to paint the whole range [first, last] or return -1 if it's impossible.
Example:
[first, last] = [0, 5] and set of triples are [[0, 5, 10], [0, 4, 1], [0, 2, 5], [2, 5, 1]]. Clearly the answer is to take [0, 4, 1] and [2, 5, 1] - the total cost will be 2.
Another example:
[first, last] = [0, 5] and triples are [[1, 4, 10], [2, 5, 6]]. Answer is -1.
太长不翻译。
1. 询问
fl一定是first, last的子区间吗？假设是。也就是说不会超出那个范围。
2. 分析
问题探析
这道题并没有直观的暴力破解手段，因为要求的是用最低cost。
一看这道题，和区间还是相关，可以考虑先对区间进行排序。首先肯定是对f进行升序排列，至于之后需不需要对l进行排序，还不能确定。
那么，至少就可以看到一种解法：每次把当前可能选取的区间都拿出来，然后进行递归。可以认为初始区间是[first, first]，每次递归那些f小于等于当前区间的l的区间。因为假设已经认为不会超过范围，因此最后结束的时候必定是以last做结尾的，这时候就可以记录下cost。最终选择最小的cost即可。
排序是O(nlogn)。递归的具体时间复杂度好像很难看出来的样子，另外空间复杂度肯定也大于O(n)。
DP解法
上面那种解法属于比较自然的解法，其实这个题也可以用DP来解。Dp[i]用来表示从first到i这个区间的最小cost。显然题目要求的解就是Dp[last]。
可以预期的是很多Dp项不会有值。因此其递推公式是范围相关的。具体来说，就是在i之前的范围里面去找l大于等于i+1的，然后和Dp[i]的cost相加，假如比当前Dp[l]的cost要小，就替换之。为了方便挑，需要对l排序。这样做的时间复杂度是O(tn)，t是区间长度，n是给的triples的个数。空间复杂度是O(n)。初始值就是Dp[first] = 0.
两种解法都列出来。
3. 代码
class Solution(object):
def sortL(self, L):
L.sort(key=lambda x: x[1])
return L
def sol(self, ranges, L, R):
seq = self.sortL(ranges)
dp = [0] + [-1] * (R)
for j in range(L + 1, R + 1):
minv = 0x7fffffff
i = len(seq) - 1
seq[i][0] = max(L, seq[i][0])
seq[i][1] = min(R, seq[i][1])
while i >= 0 and seq[i][1] >= j:
if seq[i][0] < j and dp[seq[i][0]] != -1 and dp[seq[i][0]] + seq[i][2] < minv:
minv = dp[seq[i][0]] + seq[i][2]
i -= 1
if minv == 0x7fffffff:
dp[j] = -1
else:
dp[j] = minv
return dp[R]
# solution 2
def sortF(self, F):
F.sort(key=lambda x: x[0])
return F
def sol2(self, ranges, L, R):
seq = self.sortF(ranges)
self.cost = 0x7fffffff
self.recur(seq, L, R, 0)
if self.cost == 0x7fffffff:
return -1
else:
return self.cost
def recur(self, seq, cur, R, cost):
if cur == R:
self.cost = min(self.cost, cost)
return
Q = []
for r in seq:
if r[0] <= cur:
Q.append(r)
else:
break
T = list(seq)
for r in Q:
T.remove(r)
self.recur(T, r[1], R, cost + r[2])
T.append(r)
4. 总结
难度medium~hard。
