【leetcode】1235. Maximum Profit in Job Scheduling

题目如下：

解题思路：很容易看出应该用动态规划。假设dp[i]为第i个工作在所有选择的工作序列中排在最后一个时可以获得的最大利润，那么有dp[i] = max(dp[i],dp[j] + profit[i] )（i.startTime >= j.endTime）。但是这样时间复杂度是O(n^2)，这无法被接受。继续寻找规律，对于dp[i]来说，我们要找的是所有endTime小于i.startTime的元素，所有我们可以按endTime升序排序，存储每个endTime可以获得的利润的最大值到一个列表中，这样的话，对于startTime来说，只要通过二分查找找到在endTime在列表中的位置，即可求得对应的最大值。

代码如下：

class Solution(object):
    def jobScheduling(self, startTime, endTime, profit):
        """
        :type startTime: List[int]
        :type endTime: List[int]
        :type profit: List[int]
        :rtype: int
        """
        import bisect
        item_list = []
        for (start,end,pro) in zip(startTime,endTime,profit):
            item_list.append((start,end,pro))
        def cmpf(v1,v2):
            if v1[1] != v2[1]:return v1[1] - v2[1]
            return v1[0] - v2[0]
        item_list.sort(cmp=cmpf)
        dp = [0] * len(item_list)
        dp[0] = item_list[0][2]

        end_time_order = []
        for i in range(len(item_list)):
            end_time_order.append(item_list[i][1])

        max_val_list = [dp[0]]
        max_val = dp[0]
        for i in range(1,len(item_list)):
            dp[i] = item_list[i][2]

            start = item_list[i][0]

            #left = bisect.bisect_left(end_time_order,start)
            right = bisect.bisect_right(end_time_order,start)
            if right == len(max_val_list) and end_time_order[right-1] <= start:
                dp[i] = max_val_list[-1] + item_list[i][2]
            elif right < len(max_val_list) and right > 0:
                dp[i] = max_val_list[right-1] + item_list[i][2]
            max_val = max(max_val,dp[i])
            max_val_list.append(max_val)
            #dp[i] = max(dp[i],dp[i-1])
        #print dp
        #print max_val_list
        return max(dp)