Giả sử có xe có capacity chỗ trống ban đầu cho hành khách. Xe chỉ chạy về phía đông, không thể quay lại. Ta có danh sách chuyến đi, trip[i] = [num_passengers, start_location, end_location], chứa thông tin chuyến thứ i: số hành khách phải đón, vị trí đón và trả. Vị trí cho bằng số km về phía đông từ vị trí ban đầu. Module trả về true nếu có thể đón trả hết hành khách cho tất cả chuyến. Nếu trips = [[2,1,5],[3,3,7]] và capacity = 5, kết quả true.
Để giải quyết, ta làm theo các bước −
- tạo mảng stops kích thước 1000, điền 0
- với i trong trips
- stops[i[1]] := stops[i[1]] + i[0]
- stops[i[2]] := stops[i[1]] - i[0]
- với i trong stops
- capacity := capacity - i
- nếu capacity < 0, trả về false
- trả về true khi capacity >= 0
Xem triển khai sau −
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
Kết quả
True