lc-2136-earliest-possible-day-of-full-bloom.org

LC 2136. 全部开花的最早一天

https://leetcode-cn.com/problems/earliest-possible-day-of-full-bloom/

这题大致框架是进行二分，判断某个时间t是否满足。

• 用 `t - growTime[i]` 可以判断第 i 个植物 `最晚的植入时间`
• 对植入时间进行排序，可以认为是针对最紧迫的植物先种植
• 判断是否所有的植物都可以在 `最晚的植入时间` 之前种植上

class Solution:
    def earliestFullBloom(self, plantTime: List[int], growTime: List[int]) -> int:
        n = len(plantTime)
        MaxTime = sum(plantTime) + max(growTime)

        def test(t):
            ps = []
            for i in range(n):
                relax = t - growTime[i]
                ps.append((plantTime[i], relax))
            ps.sort(key=lambda x: x[1])
            acc = 0
            for i in range(n):
                acc += ps[i][0]
                if acc > ps[i][1]:
                    return False
            return True

        s, e = 0, MaxTime
        while s <= e:
            m = (s + e) // 2
            if test(m):
                e = m - 1
            else:
                s = m + 1
        return s