Giả sử chúng ta có một ma trận được gọi là request_trips trong đó mỗi hàng chứa [start_x, end_x, num_passengers] và chúng ta cũng có một giá trị dung lượng. Giờ đây, mỗi chuyến đi được yêu cầu sẽ yêu cầu đón hành khách num_passengers tại start_x và trả khách lúc end_x. Chúng tôi cũng có một chiếc ô tô với sức chứa đã cho, xuất phát ở vị trí x =0. Chúng tôi muốn đón mọi hành khách và chỉ có thể di chuyển bên phải, chúng tôi phải kiểm tra xem chúng tôi có thể đón và trả tất cả mọi người hay không.
Vì vậy, nếu đầu vào giống như chuyến đi =[[1, 25, 2], [3, 4, 3], [5, 12, 3]] dung lượng =6, thì đầ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 -
-
sự kiện:=một danh sách mới
-
cho mỗi tập hợp (sx, ex, np) trong các chuyến đi, thực hiện
-
chèn cặp (sx, np) vào cuối sự kiện
-
chèn cặp (ví dụ, −np) vào cuối sự kiện
-
-
mang:=0
-
đối với mỗi cặp (loc, delta) trong danh sách các sự kiện (theo thứ tự đã sắp xếp), thực hiện
-
mang:=mang + đồng bằng
-
nếu mang> công suất thì
-
trả về Sai
-
-
-
trả về True
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, trips, capacity): events = [] for sx, ex, np in trips: events.append((sx, np)) events.append((ex, -np)) carrying = 0 for loc, delta in sorted(events): carrying += delta if carrying > capacity: return False return True ob = Solution() trips = [ [1, 25, 2], [3, 4, 3], [5, 12, 3] ] capacity = 6 print(ob.solve(trips, capacity))
Đầu vào
trips = [ [1, 25, 2], [3, 4, 3], [5, 12, 3] ] capacity = 6
Đầu ra
True