【LeetCode】12. 小张刷题计划

稳住，能赢！没有经验的同学在面试岗位的时候，总是显得手忙脚乱，所以多练习，把技能提升，眼界提升，接着心态放平和，不要慌张，把面试题目读懂读透彻就会大大提升赢的概率。

1. 题目

本题质量不错，是一道很好的二分法面试题。

2. 分析

2.1 贪心

本题是求小张做题时间最多的一天耗时，不是求总共耗时，所以贪心的方法解这题不行。也就是说下面这个方法是无法得到正确答案的。

class Solution:
    def minTime(self, time: List[int], m: int) -> int:
        time.sort(reverse=True)
        res = sum(time[m::])
        return res

2.2 二分法

本题如果去掉求助这一环节，那么就是一道典型的二分法题，但是加上了“求助” 这么一个操作，二分法依然可解。只不过是带上了一点儿限制条件：这个限制条件就是去除掉每天的做题中耗时最久的那道题。

在得到这个限制条件后，唯一的判断条件就是：在当前这个“每天的最大做题量”情况下，是否能在要求的天数内完成做题？这么来看，就是一道比较典型的二分法求解题了。

3. 代码

class Solution:
    def minTime(self, time: List[int], m: int) -> int:
        left, right = 0, sum(time)
        while(left <= right):
            mid = (left + right) // 2 
            print(left, right, mid)
            if self.check(mid, time, m):
                right = mid - 1
            else: 
                left = mid + 1    
        return left

    # 每天耗时limit的情况下，是否能在m天内完成
    def check(self, limit, time, m):        
        need = 0
        cur_max = 0 # 某一个窗口内的最大耗时        
        total = 0
        for i in range(len(time)):
            cur_max = max(cur_max, time[i])
            if total + time[i] - cur_max <= limit:
                total += time[i]
            else: # 重置。（又是新的一天）
                need += 1
                cur_max = time[i]
                total = time[i]
        if total:
            need += 1
        return m>=need