Giả sử ban đầu có một chiếc xe có sức chứa ghế trống cho hành khách. Xe chỉ chạy về hướng đông, vì vậy chúng tôi không thể quay đầu và lái xe về hướng tây. Chúng tôi đã đưa ra danh sách các chuyến đi, chuyến đi [i] =[num_passengers, start_location, end_location], chứa thông tin về chuyến đi thứ i :, vì vậy đó là số lượng hành khách phải đón và địa điểm đón họ và thả chúng ra. Ở đây, các vị trí được đưa ra là số km về phía đông tính từ vị trí ban đầu của xe của chúng tôi. Mô-đun của chúng tôi sẽ trả về true nếu và chỉ khi có thể đón và trả tất cả hành khách cho tất cả các chuyến đi nhất định. Vì vậy, nếu các chuyến đi giống như [[2,1,5], [3,3,7]] và công suất là 5, thì kết quả đầu ra sẽ là true.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- tạo một mảng được gọi là điểm dừng, có kích thước 1000 và điền vào mảng này bằng 0
- cho tôi trong các chuyến đi
- điểm dừng [i [1]]:=điểm dừng [i [1]] + i [0]
- điểm dừng [i [2]]:=điểm dừng [i [1]] - tôi [0]
- cho tôi trong các điểm dừng -
- dung lượng:=công suất - i
- nếu dung lượng <0, thì trả về false
- trả về true khi dung lượng> =0
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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))
Đầu vào
[[2,1,5],[3,3,7]] 5
Đầu ra
True