1094.拼车

链接：1094.拼车
难度：Medium
标签：数组、前缀和、排序、模拟、堆（优先队列）
简介：当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false。

题解 1 - python

• 编辑时间：2023-12-02
• 执行用时：40ms
• 内存消耗：16.64MB
• 编程语言：python
• 解法介绍：排序后优先队列计数。

class Solution:
    def carPooling(self, trips: List[List[int]], capacity: int) -> bool:
        trips.sort(key = lambda o: (o[1], o[2]))
        size = 0
        q = []
        for [num, f, t] in trips:
            while q and q[0][0] <= f: size -= heappop(q)[1]
            if size + num > capacity: return False
            heappush(q, (t, num))
            size += num
        return True

题解 2 - rust

• 编辑时间：2023-12-02
• 内存消耗：2.07MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn car_pooling(mut trips: Vec<Vec<i32>>, capacity: i32) -> bool {
        trips.sort_by_key(|o| o[1]);
        let mut size = 0;
        let mut q = std::collections::BinaryHeap::<(i32, i32)>::new();
        for item in trips {
            let (num, f, t) = (item[0], item[1], item[2]);
            while q.len() > 0 && -(*q.peek().unwrap()).0 <= f {
                size -= q.pop().unwrap().1;
            }
            if size + num > capacity {
                return false;
            }
            q.push((-t, num));
            size += num;
        }
        true
    }
}