План курса / Все задачи / Алгоритмы и структуры данных
Вместимость автобуса
средне
# решено
Дан массив trips, где каждый элемент trips[i] = [from, to, passengers] описывает поездку: from — точка посадки, to — точка высадки, passengers — количество пассажиров. Также дано число capacity — максимальное количество пассажиров, которое может перевозить автобус.
Нужно вернуть true, если водитель автобуса сможет перевезти всех пассажиров, не превышая capacity, и false в противном случае.
public class Solution {
public static bool BusCapacity(List<List<int>> trips, int capacity) {
List<(int, int)> points = new List<(int, int)>();
foreach (var trip in trips) {
// Добавляем точку, где пассажиры заходят (from, passengers)
points.Add((trip[0], trip[2]));
// Добавляем точку, где пассажиры выходят (to, -passengers)
points.Add((trip[1], -trip[2]));
}
// Сортируем точки по координате
// Если координаты равны, сначала обрабатываем выход пассажиров, затем вход
points.Sort((a, b) => {
if (a.Item1 == b.Item1) return a.Item2.CompareTo(b.Item2);
return a.Item1.CompareTo(b.Item1);
});
int currPassengers = 0;
foreach (var point in points) {
// Обновляем текущее количество пассажиров
currPassengers += point.Item2;
// Если превышена вместимость, возвращаем false
if (currPassengers > capacity) {
return false;
}
}
// Если ни в одной точке не превышена вместимость, возвращаем true
return true;
}
}
#include <vector>
#include <algorithm>
using namespace std;
bool busCapacity(vector<vector<int>> trips, int capacity) {
vector<pair<int, int>> points;
for (auto trip : trips) {
// Добавляем точку, где пассажиры заходят (from, passengers)
points.push_back({trip[0], trip[2]});
// Добавляем точку, где пассажиры выходят (to, -passengers)
points.push_back({trip[1], -trip[2]});
}
// Сортируем точки по координате
// Если координаты равны, сначала обрабатываем выход пассажиров, затем вход
sort(points.begin(), points.end(), [](pair<int, int> a, pair<int, int> b) {
if (a.first == b.first) return a.second < b.second;
return a.first < b.first;
});
int currPassengers = 0;
for (auto point : points) {
// Обновляем текущее количество пассажиров
currPassengers += point.second;
// Если превышена вместимость, возвращаем false
if (currPassengers > capacity) {
return false;
}
}
// Если ни в одной точке не превышена вместимость, возвращаем true
return true;
}
package main
import (
"sort"
)
func busCapacity(trips [][]int, capacity int) bool {
type Point struct {
Time int
Delta int
}
var points []Point
for _, trip := range trips {
// Добавляем точку, где пассажиры заходят (from, passengers)
points = append(points, Point{trip[0], trip[2]})
// Добавляем точку, где пассажиры выходят (to, -passengers)
points = append(points, Point{trip[1], -trip[2]})
}
// Сортируем точки по координате
// Если координаты равны, сначала обрабатываем выход пассажиров, затем вход
sort.Slice(points, func(i, j int) bool {
if points[i].Time == points[j].Time {
return points[i].Delta < points[j].Delta
}
return points[i].Time < points[j].Time
})
currPassengers := 0
for _, point := range points {
// Обновляем текущее количество пассажиров
currPassengers += point.Delta
// Если превышена вместимость, возвращаем false
if currPassengers > capacity {
return false
}
}
// Если ни в одной точке не превышена вместимость, возвращаем true
return true
}
import java.util.*;
public class Solution {
public boolean busCapacity(List<List<Integer>> trips, int capacity) {
List<int[]> points = new ArrayList<>();
for (List<Integer> trip : trips) {
// Добавляем точку, где пассажиры заходят (from, passengers)
points.add(new int[]{trip.get(0), trip.get(2)});
// Добавляем точку, где пассажиры выходят (to, -passengers)
points.add(new int[]{trip.get(1), -trip.get(2)});
}
// Сортируем точки по координате
// Если координаты равны, сначала обрабатываем выход пассажиров, затем вход
points.sort((a, b) -> {
if (a[0] == b[0]) return Integer.compare(a[1], b[1]);
return Integer.compare(a[0], b[0]);
});
int currPassengers = 0;
for (int[] point : points) {
// Обновляем текущее количество пассажиров
currPassengers += point[1];
// Если превышена вместимость, возвращаем false
if (currPassengers > capacity) {
return false;
}
}
// Если ни в одной точке не превышена вместимость, возвращаем true
return true;
}
}
from typing import List
def bus_capacity(trips: List[List[int]], capacity: int) -> bool:
points = []
for trip in trips:
# Добавляем точку, где пассажиры заходят (from, passengers)
points.append([trip[0], trip[2]])
# Добавляем точку, где пассажиры выходят (to, -passengers)
points.append([trip[1], -trip[2]])
# Сортируем точки по координате
# Если координаты равны, сначала обрабатываем выход пассажиров, затем вход
points.sort(key=lambda x: (x[0], x[1]))
curr_passengers = 0
for point in points:
# Обновляем текущее количество пассажиров
curr_passengers += point[1]
# Если превышена вместимость, возвращаем False
if curr_passengers > capacity:
return False
# Если ни в одной точке не превышена вместимость, возвращаем True
return True
export function busCapacity(trips, capacity) {
let points = [];
for (let trip of trips) {
// Добавляем точку, где пассажиры заходят (from, passengers)
points.push([trip[0], trip[2]]);
// Добавляем точку, где пассажиры выходят (to, -passengers)
points.push([trip[1], -trip[2]]);
}
// Сортируем точки по координате
// Если координаты равны, сначала обрабатываем выход пассажиров, затем вход
points.sort((a, b) => {
if (a[0] === b[0]) return a[1] - b[1];
return a[0] - b[0];
});
let currPassengers = 0;
for (let point of points) {
// Обновляем текущее количество пассажиров
currPassengers += point[1];
// Если превышена вместимость, возвращаем false
if (currPassengers > capacity) {
return false;
}
}
// Если ни в одной точке не превышена вместимость, возвращаем true
return true;
}