esc to dismiss

1094. 拼车

题目

假设你是一位顺风车司机,车上最初有 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

解体思路

这道题目跟航班预订、排课计划等题目类似,首先最容易想到的是定义一个数组,记录所有的站点人数,如果有站点人数超过容量,则返回false,否则true。

这样就需要两个循环,一个循环是trips的外循环,一个是内部循环从 start_location 到 end_location。 这种算法很容易理解,但是效率低。

合理的解法是利用 差分 算法:

func carPooling(trips [][]int, capacity int) bool {
    var stops [1001]int

    for _, t := range trips {
        stops[t[1]] += t[0]
        stops[t[2]] -= t[0]
    }

    sum := 0
    for _, c := range stops {
        sum += c
        if sum > capacity {
            return false
        }
    }

    return true
}

还是需要定义 stops 数组,但是不需要对每个 stop 计算人数,而只是在 start_location 处加人,在 end_location 处减人。然后怎么统计 stop 的人数呢:

遍历这个stops数组,定义一个 sum 计数,累加循环变量,如果sum在过程中超过了容量,则返回false,否则最后返回true。想象一下,就像一辆地铁列车,用一个计数器,每一站加上到站的上车人数,减去下车人数,那么这个计数器就能反映每站的实际人数。

经验教训

考试时遇到过类似的题,当时不知道差分,只会用暴力,结果性能用例没有过,都是泪。

x