No.0017-CareerCup

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。

No.0017-CareerCup