原文链接: https://leetcode-cn.com/problems/car-pooling

英文原文

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trip[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

 

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Example 3:

Input: trips = [[2,1,5],[3,5,7]], capacity = 3
Output: true

Example 4:

Input: trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
Output: true

 

Constraints:

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 105

中文题目

假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：

• 必须接送的乘客数量；
• 乘客的上车地点；
• 以及乘客的下车地点。

这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

 

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false

示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true

示例 3：

输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true

示例 4：

输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true

 

提示：

• 你可以假设乘客会自觉遵守 “先下后上” 的良好素质
• trips.length <= 1000
• trips[i].length == 3
• 1 <= trips[i][0] <= 100
• 0 <= trips[i][1] < trips[i][2] <= 1000
• 1 <= capacity <= 100000

通过代码

高赞题解

第一个思路是一下就想到的，把一路上的负载数组构造出来，比较什么时候负载超重，就可以了

public boolean carPooling(int[][] trips, int capacity) {

    int[] allTrip = new int[1001];

    for (int i = 0; i < trips.length; i++) {

        for (int j = trips[i][1]; j < trips[i][2]; j++) {

            allTrip[j] += trips[i][0];

            if (allTrip[j] > capacity) {

                return false;

            }

        }

    }

    return true;

}

或者换一个思路，直接记录上下车的容量变化情况，内存没变化，但是效率提升很快

public boolean carPooling(int[][] trips, int capacity) {

    int[] capacityChanges = new int[1001];

    for (int i = 0; i < trips.length; i++) {

        capacityChanges[trips[i][1]] -= trips[i][0];

        capacityChanges[trips[i][2]] += trips[i][0];

    }



    for (int i = 0;i < capacityChanges.length;i++) {

        capacity += capacityChanges[i];

        if (capacity < 0) {

            return false;

        }

    }

    return true;

}

统计信息

通过次数	提交次数	AC比率
30059	50288	59.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
会议室 II	中等