1094. 拼车

1094. 拼车

• 难度: medium
• 原始链接: https://leetcode.cn/problems/car-pooling
• 标签: 堆排序, 差分数组

解法一: 堆排序

java

class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        Arrays.sort(trips, (arr1, arr2) -> arr1[1] - arr2[1]);
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>((arr1, arr2) -> arr1[2] - arr2[2]);
        int peopleCount = 0;
        for (int[] trip : trips) {
            while (!priorityQueue.isEmpty() && trip[1] >= priorityQueue.peek()[2]) {
                peopleCount -= priorityQueue.poll()[0];
            }
            priorityQueue.offer(trip);
            peopleCount += trip[0];
            if (peopleCount > capacity) {
                return false;
            }
        }
        return true;
    }
}

解法二: 差分数组

go

func carPooling(trips [][]int, capacity int) bool {
    arr := make([]int, 1001)
    for _, trip := range trips {
        arr[trip[1]] += trip[0]
        arr[trip[2]] -= trip[0]
    }
    sum := 0
    for _, num := range arr {
        sum += num
        if sum > capacity {
            return false
        }
    }
    return true
}