🔒Открыть пост
и посмотреть медиа
и посмотреть медиа
Задача: 1094. Car Pooling
Сложность: 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 {
function carPooling($trips, $capacity) {
$timestamp = [];
foreach ($trips as $trip) {
$timestamp[$trip[1]] = ($timestamp[$trip[1]] ?? 0) + $trip[0];
$timestamp[$trip[2]] = ($timestamp[$trip[2]] ?? 0) - $trip[0];
}
ksort($timestamp);
$usedCapacity = 0;
foreach ($timestamp as $change) {
$usedCapacity += $change;
if ($usedCapacity > $capacity) {
return false;
}
}
return true;
}
}
Ставь 👍 и забирай 📚 Базу знаний
