小张刷题计划

标签: 数组 二分查找

难度: Medium

为了提高自己的代码能力，小张制定了 LeetCode 刷题计划，他选中了 LeetCode 题库中的 n 道题，编号从 0 到 n-1，并计划在 m 天内按照题目编号顺序刷完所有的题目（注意，小张不能用多天完成同一题）。

在小张刷题计划中，小张需要用 time[i] 的时间完成编号 i 的题目。此外，小张还可以使用场外求助功能，通过询问他的好朋友小杨题目的解法，可以省去该题的做题时间。为了防止“小张刷题计划”变成“小杨刷题计划”，小张每天最多使用一次求助。

我们定义 m 天中做题时间最多的一天耗时为 T（小杨完成的题目不计入做题总时间）。请你帮小张求出最小的 T是多少。

示例 1：

输入：time = [1,2,3,3], m = 2

输出：3

解释：第一天小张完成前三题，其中第三题找小杨帮忙；第二天完成第四题，并且找小杨帮忙。这样做题时间最多的一天花费了 3 的时间，并且这个值是最小的。

示例 2：

输入：time = [999,999,999], m = 4

输出：0

解释：在前三天中，小张每天求助小杨一次，这样他可以在三天内完成所有的题目并不花任何时间。

限制：

  • 1 <= time.length <= 10^5
  • 1 <= time[i] <= 10000
  • 1 <= m <= 1000

Submission

运行时间: 214 ms

内存: 26.5 MB

class Solution:
    def f(self,T,time):
        cnt,s=1,0
        max_time=0
        for i in time:
            if i > max_time:
                s+=max_time
                max_time=i
            else:
                s+=i

            if s > T:
                s = 0
                max_time = i
                cnt+=1
            # print(T,s)
        return cnt

    def minTime(self, time: List[int], m: int) -> int:

        low,up = 0, sum(time)
        while low < up:
            mid = (low+up)//2

            if self.f(mid, time) > m:
                low = mid+1
            else:
                up=mid

        return low

Explain

题解采用了二分查找结合贪心算法的策略。首先定义f函数，该函数用于判断在最大单日时间T的限制下，小张完成所有题目需要的天数。对于每道题，我们维护当前天的总时间s和当天最耗时的题目时间max_time。如果添加新题会使总时间s超过T，那么新开一天，并将当前题作为新一天的第一题。在minTime函数中，通过调整T的值（二分查找）来找到使得f函数返回的天数不超过m的最小T值。

时间复杂度: O(n log(sum(time)))

空间复杂度: O(1)

class Solution:
    def f(self,T,time):
        cnt,s=1,0  # 初始化天数为1，当前天的总时间为0
        max_time=0  # 初始化当前天的最长单题时间
        for i in time:
            if i > max_time:
                s+=max_time  # 将之前的最长时间加入总时间
                max_time=i  # 更新最长时间为当前题目时间
            else:
                s+=i  # 将当前题目时间加入总时间

            if s > T:  # 当总时间超过T时，开启新的一天
                s = 0  # 重置当天总时间
                max_time = i  # 设置当前题目为新一天的第一题
                cnt+=1  # 天数增加
        return cnt

    def minTime(self, time: List[int], m: int) -> int:

        low,up = 0, sum(time)  # 二分搜索的起始和结束点
        while low < up:
            mid = (low+up)//2  # 计算中点

            if self.f(mid, time) > m:  # 如果需要的天数超过m
                low = mid+1  # 调整搜索范围的下界
            else:
                up=mid  # 调整搜索范围的上界

        return low  # 返回最小的T

Explore

在这个题解中，`low` 设为 0 实际上可能不是最优的选择，因为一个更合理的起始值应该是题目中的最小耗时。这样设定是因为，我们在考虑任何合法的单日时间 `T` 时，至少应保证 `T` 不小于任何单个题目的耗时，以确保每个题目都可以在某一天被完成。如果 `low` 设置为 0，则在函数 `f` 中会有额外的判断和处理，确保不会出现无法分配题目的情况。因此，从理论和实用角度看，将 `low` 设置为 `time` 中的最小值是更合适的，这可以减少二分查找的范围并提高效率。

使用 `max_time` 来记录最耗时的题目的策略可能在题目的时间分布不均时导致不必要的天数增加。例如，如果一天中开始就遇到一个极端耗时的题目，后续题目耗时都很短，这种策略会导致该天只能完成很少的题目，而实际上将一些短的题目安排在耗时题目的同一天可能是可行的。这样就可能增加总天数，尤其是当耗时最长的题目和其他题目的耗时差异很大时更为明显。

选择 `sum(time)` 作为上界是因为这是在极端情况下，即不将任何题目分到不同天，一个人在一天内尝试完成所有题目的总耗时。虽然从实际情况来看，这通常不是一个有效的策略，因为这样会导致需要的天数为1，这通常不可能满足题目的其他限制（如天数限制 `m`）。然而，将上界设置为 `sum(time)` 确保了二分搜索能覆盖所有可能的 `T` 值，从最小可能的 `T`（题目耗时的最小值）到最大可能的 `T`（所有题目耗时之和）。