Python 中的拼车问题

假设有一辆车，一开始有 capacity 个空座位供乘客使用。该车只向东行驶，所以我们不能掉头向西行驶。我们给定了一个行程列表 trips，其中 trip[i] = [num_passengers, start_location, end_location]，包含有关第 i 次行程的信息：num_passengers 是必须接送的乘客数量，以及接送他们的位置。此处的 location 是指从我们的车辆初始位置向东行驶的公里数。当且仅当接送所有乘客的所有已给定行程均可行时，我们的模块才会返回 True。因此，如果行程为 [[2,1,5],[3,3,7]]，容量为 5，则输出将为 true。

为了解决这个问题，我们将按照以下步骤进行 −

• 制作一个名为 stops 的数组，大小为 1000，并用 0 填充
• 对于行程中的 i
  • stops[i[1]] := stops[i[1]] + i[0]
  • stops[i[2]] := stops[i[1]] – i[0]
• 对于 stops 中的 i −
  • capacity := capacity – i
  • 如果 capacity < 0，则返回 false
• 当容量 >= 0 时返回真

让我们参阅下列实现以加深理解 −

示例

 动态演示

class Solution(object):
   def carPooling(self, trips, capacity):
      stops = [0 for i in range(1001)]
      for i in trips:
         stops[i[1]]+=i[0]
         stops[i[2]]-=i[0]
      for i in stops:
         capacity-=i
         if capacity<0:
            return False
      return capacity>=0
ob = Solution()
print(ob.carPooling([[2,1,5],[3,3,7]],5))

输入

[[2,1,5],[3,3,7]]
5

输出

True

Arnab Chakraborty

更新时间: 30-4 月-2020

666 查看次数

开始你的 职业

通过完成课程获得认证

开始