吃掉所有谷子的最短时间

Submission

运行时间: 239 ms

内存: 17.2 MB

class Solution:
    def minimumTime(self, hens: List[int], grains: List[int]) -> int:
        def check(t):
            j = 0
            for x in hens:
                if j == m:
                    return True
                y = grains[j]
                if y <= x:
                    d = x - y
                    if d > t:
                        return False
                    while j < m and grains[j] <= x:
                        j += 1
                    while j < m and min(d, grains[j] - x) + grains[j] - y <= t:
                        j += 1
                else:
                    while j < m and grains[j] - x <= t:
                        j += 1
            return j == m

        hens.sort()
        grains.sort()
        m = len(grains)
        r = abs(hens[0] - grains[0]) + grains[-1] - grains[0] + 1
        return bisect_left(range(r), True, key=check)

Explain

本题解采用了二分查找与贪心算法的结合。首先对鸡和谷子的位置进行排序，以便于之后的计算。定义了一个辅助函数 `check(t)` 来判断鸡在时间 `t` 内是否能吃掉所有的谷子。在这个函数中，分别处理当谷子位置在鸡的位置之前和之后的情况，确保每只鸡在时间 `t` 内可以贪心地尽可能多吃掉谷子。最后使用二分查找来确定最小的时间 `t`，使得所有的鸡都能在这个时间内吃完所有的谷子。

时间复杂度: O(n log(r))

空间复杂度: O(n)

class Solution:
    def minimumTime(self, hens: List[int], grains: List[int]) -> int:
        def check(t):
            j = 0
            for x in hens:
                if j == m:
                    return True
                y = grains[j]
                if y <= x:
                    d = x - y
                    if d > t:
                        return False
                    while j < m and grains[j] <= x:
                        j += 1
                    while j < m and min(d, grains[j] - x) + grains[j] - y <= t:
                        j += 1
                else:
                    while j < m and grains[j] - x <= t:
                        j += 1
            return j == m

        hens.sort()  # 对鸡的位置进行排序
        grains.sort()  # 对谷子的位置进行排序
        m = len(grains)  # 谷子的数量
        r = abs(hens[0] - grains[0]) + grains[-1] - grains[0] + 1  # 计算可能的最大时间范围
        return bisect_left(range(r), True, key=check)  # 使用二分查找确定最小时间

Explore

在处理谷子位置在鸡位置之前和之后的时，选择的条件和迭代方式不同是为了最大化贪心策略的效率。当谷子位于鸡的位置之前时，鸡需要向左移动来吃到谷子，这时我们关心的是鸡能向左移动的最大距离是否小于等于时间`t`。如果鸡的位置大于谷子的位置超过`t`，那么鸡在`t`时间内无法吃到这个谷子，算法直接返回`False`。如果鸡可以到达谷子位置，我们继续追踪鸡向左移动后能额外向右移动的范围，以尽可能多地吃到后续的谷子。相反，当谷子位于鸡的位置之后时，鸡向右移动，我们只需检查鸡是否能在`t`时间内直接到达谷子的位置。这种区分处理方式帮助算法针对不同情景采用最有效的策略，从而提高整体的执行效率。这种差异化处理显著提高了算法的性能，使其能更快地找到满足条件的最小`t`值，同时确保算法结果的正确性。