列表

详情

1094. 拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向）

给定整数 capacity 和一个数组 trips ,  trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客，接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。

当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

 

示例 1：

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

示例 2：

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

 

提示：

相似题目

会议室 II

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: bool carPooling(vector<vector<int>>& trips, int capacity) { } };

javascript 解法, 执行用时: 64 ms, 内存消耗: 42.7 MB, 提交时间: 2023-12-02 00:05:55 

/**
 * @param {number[][]} trips
 * @param {number} capacity
 * @return {boolean}
 */
var carPooling = function(trips, capacity) {
    let to_max = 0;
    for (const trip of trips) {
        to_max = Math.max(to_max, trip[2]);
    }

    const diff = new Array(to_max + 1).fill(0);
    for (const trip of trips) {
        diff[trip[1]] += trip[0];
        diff[trip[2]] -= trip[0];
    }

    let count = 0;
    for (let i = 0; i <= to_max; ++i) {
        count += diff[i];
        if (count > capacity) {
            return false;
        }
    }
    return true;
};

golang 解法, 执行用时: 4 ms, 内存消耗: 3.4 MB, 提交时间: 2023-12-02 00:05:38 

func carPooling(trips [][]int, capacity int) bool {
    toMax := 0
    for _, trip := range trips {
        toMax = max(toMax, trip[2])
    }
    
    diff := make([]int, toMax + 1)
    for _, trip := range trips {
        diff[trip[1]] += trip[0]
        diff[trip[2]] -= trip[0]
    }

    count := 0
    for i := 0; i < toMax; i++ {
        count += diff[i]
        if count > capacity {
            return false
        }
    }
    return true
}

cpp 解法, 执行用时: 8 ms, 内存消耗: 10.6 MB, 提交时间: 2023-12-02 00:04:56 

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        vector<int> d(1002);
        for(auto &e: trips) {
            d[e[1]] += e[0];
            d[e[2]] -= e[0];
        }
        for(int i = 0; i <= 1000; i ++ ) {
            if(i) d[i] += d[i - 1];
            if(d[i] > capacity) return false;
        }
        return true;
    }
};

python3 解法, 执行用时: 36 ms, 内存消耗: 15.3 MB, 提交时间: 2022-12-10 13:44:52 

from typing import List
import heapq


class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key=lambda x: x[1])
        off_dist = []
        count = 0
        for i in range(len(trips)):
            dist = trips[i][1]
            while off_dist and dist >= off_dist[0][0]:
                _, passenger = heapq.heappop(off_dist)
                count -= passenger
            count += trips[i][0]
            if count > capacity:
                return False
            heapq.heappush(off_dist, [trips[i][-1], trips[i][0]])
        return True


    def carPooling1(self, trips: List[List[int]], capacity: int) -> bool:
        stop = []
        for n, s, e in trips:
            stop.append([s, n])
            stop.append([e, -n])

        stop.sort()

        for _, count in stop:
            capacity -= count
            if capacity < 0: return False

        return True

python3 解法, 执行用时: 32 ms, 内存消耗: 15.4 MB, 提交时间: 2022-12-10 13:44:25 

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        ##因为trips长度最大为1000，为了用位置进行索引，创建1001长度的数组
        f = [0 for i in range(1002)]
        for x, start, end in trips:
            f[start] += x
            f[end] -= x
        p = 0
        for i in range(len(f)):
            p += f[i]  ##第i个位置时，车上的人数
            if p>capacity:
                return False
        return True

java 解法, 执行用时: 1 ms, 内存消耗: 41.5 MB, 提交时间: 2022-12-10 13:43:01 

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        int sites[] = new int[1001];
        for (int[] trip : trips) {
            // 上车加
            sites[trip[1]] += trip[0];
            // 下车减
            sites[trip[2]] -= trip[0];
        }
        // 从始发站计数，超过capacity则超载
        int total = 0;
        for (int i : sites) {
            total += i;
            if (total > capacity) {
                return false;
            }
        }
        return true;
    }
}

上一题

© 2024 leetcode.cn