Сложность: medium
Есть автомобиль с пустыми сиденьями емкостью capacity. Автомобиль движется только на восток (то есть он не может повернуть и ехать на запад).
Дан целочисленный параметр capacity и массив поездок trips, где trips[i] = [numPassengersi, fromi, toi] указывает, что на i-й поездке numPassengersi пассажиров должны быть забраны на позиции fromi и высажены на позиции toi. Позиции заданы как количество километров на восток от начальной точки автомобиля.
Верните true, если возможно забрать и высадить всех пассажиров для всех указанных поездок, или false в противном случае.
Пример:
Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false
👨💻 Алгоритм:
1⃣Простая идея заключается в том, чтобы пройти от начала до конца и проверить, превышает ли фактическая вместимость capacity.
2⃣Чтобы узнать фактическую вместимость, нужно просто знать изменение количества пассажиров в каждый момент времени.
3⃣Мы можем сохранить изменения количества пассажиров в каждый момент времени, отсортировать их по меткам времени и, наконец, пройтись по ним, чтобы проверить фактическую вместимость.
😎 Решение:
class Solution:
def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
timestamp = {}
for trip in trips:
timestamp[trip[1]] = timestamp.get(trip[1], 0) + trip[0]
timestamp[trip[2]] = timestamp.get(trip[2], 0) - trip[0]
used_capacity = 0
for time in sorted(timestamp):
used_capacity += timestamp[time]
if used_capacity > capacity:
return False
return True
Ставь 👍 и забирай 📚 Базу знаний