题目
车上最初有
capacity个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）给定整数
capacity和一个数组trips,trip[i] = [numPassengersi, fromi, toi]表示第i次旅行有numPassengersi乘客，接他们和放他们的位置分别是fromi和toi。这些位置是从汽车的初始位置向东的公里数。当且仅当你可以在所有给定的行程中接送所有乘客时，返回
true，否则请返回false。
解题思路
- 车不允许掉头和改变方向，所以需要重最近位置开始接客；
- 根据上车位置对乘客进行排序；
- 遍历排序后的数组，通过map存储当前车上的乘客下车位置和人数；
- 通过list记录哪些位置有乘客下车，并在之后从map中删除该数据；
- 根据上下车乘客对座位进行加减，当座位小于0时则失败；
代码展示
class Solution { public boolean carPooling(int[][] trips, int capacity) { //根据起始位置对数组进行排序 Arrays.sort(trips, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[1] - o2[1]; } }); //记录在哪个位置下去多少人 Map<Integer,Integer> store = new HashMap<>(); for (int i = 0; i < trips.length; i++){ //存储已经下车的 List<Integer> data = new ArrayList<>(); for (Integer num : store.keySet()){ if (trips[i][1] >= num){ //释放空座位，清除已下车的人 capacity += store.get(num); data.add(num); } } for (Integer num : data){ store.remove(num); } capacity -= trips[i][0]; store.put(trips[i][2], store.getOrDefault(trips[i][2], 0) + trips[i][0]); if(capacity < 0){ return false; } } return true; } }
