3633-最早完成陆地和水上游乐设施的时间 I

题目描述

给你四个下标从 0 开始的整数数组 landStartTime、landDuration、waterStartTime 和 waterDuration，其中 landStartTime[i] 和 landDuration[i] 分别表示第 i 个陆地游乐设施的开始时间和持续时间，而 waterStartTime[j] 和 waterDuration[j] 分别表示第 j 个水上游乐设施的开始时间和持续时间,求最早完成所有游乐设施的时间。

思路

枚举每次从陆地游乐设施开始还是从水上游乐设施开始的情况，计算两种情况的完成时间，取最小值。

  • 时间复杂度：O():其中和分别是陆地和水上游乐设施的数量
  • 空间复杂度：O(1)
tkzzzzzz6/Web_examclassSolution:

    defearliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:

        n =len(landStartTime)

        m =len(waterStartTime)

        res = math.inf


        for i inrange(n):

            for j inrange(m):

                land = landStartTime[i] + landDuration[i]

                land2water =max(land, waterStartTime[j]) + waterDuration[j]

                res =min(res, land2water)


                water = waterStartTime[j] + waterDuration[j]

                water2land =max(water, landStartTime[i]) + landDuration[i]

                res =min(res, water2land)


        return res

思路:线性枚举 + 分类讨论

① 找出第一类情况：先完成陆地游乐设施，再完成水上游乐设施的最早完成时间

② 找出第二类情况：先完成水上游乐设施，再完成陆地游乐设施的最早完成时间

③ 取两类情况的最小值即为最终答案

好处是避免双重循环，直接通过线性枚举和分类讨论的方式计算出两类情况的完成时间，效率更高。

  • 时间复杂度：O():其中和分别是陆地和水上游乐设施的数量
  • 空间复杂度：O(1)
classSolution:

    defsolve(self,start1,duration1,start2,duration2):

        finish1 = math.inf

        for i inrange(len(start1)):

            finish1 =min(finish1,start1[i]+ duration1[i])

  

        finish2 = math.inf

        for i inrange(len(start2)):

            finish2 =min(finish2,max(finish1,start2[i])+ duration2[i])


        return finish2


    defearliestFinishTime(self, landStartTime: List[int], landDuration: List[int], waterStartTime: List[int], waterDuration: List[int]) -> int:

        land2water =self.solve(landStartTime,landDuration,waterStartTime,waterDuration)

        water2land =self.solve(waterStartTime,waterDuration,landStartTime,landDuration)


        returnmin(land2water,water2land)