Giả sử chúng ta có một ma trận gọi là requested_trips, mỗi hàng chứa [start_x, end_x, num_passengers], và chúng ta cũng có một giá trị capacity. Mỗi chuyến yêu cầu đón num_passengers hành khách tại start_x và trả họ tại end_x. Chúng ta cũng có một chiếc xe với capacity cho trước, bắt đầu tại vị trí x = 0. Chúng ta muốn đón mọi hành khách và chỉ có thể di chuyển sang phải, chúng ta phải kiểm tra xem có thể đón và trả hết mọi người hay không.
Ví dụ, nếu đầu vào là trips = [[1, 25, 2], [3, 4, 3], [5, 12, 3]], capacity = 6, thì đầu ra sẽ là True
Để giải quyết, chúng ta thực hiện các bước sau:
- events := danh sách mới
- với mỗi bộ (sx, ex, np) trong trips:
- thêm cặp (sx, np) vào cuối events
- thêm cặp (ex, -np) vào cuối events
- carrying := 0
- với mỗi cặp (loc, delta) trong danh sách events (đã sắp xếp), thực hiện:
- carrying := carrying + delta
- nếu carrying > capacity, trả về False
- trả về True
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))
Input
trips = [ [1, 25, 2], [3, 4, 3], [5, 12, 3] ] capacity = 6
Output
True