这道题目的模型其实很简单,可以理解为动态维护一个有限的容器(例如堆栈等计算资源)。
而按照题意直接进行解答的思路当然就如下:
对每一个计划,需要执行一次遍历,更新当前所有位置上的状态并判断。
此时解决问题的复杂度与计划数量及计划区间成正比,显然 weak scalable。
一个比较高效的思路是:将行程信息预处理,这样可以得知在每一站的使用量净值变化(充分利用该问题的离散特点)。这样在预处理后的复杂度将只和站数有关。(对应于资源使用量可以进行动态监测而不会产生较大的性能波动)
下面是一份简单的python3实现代码。
|
|
假设起点与终点距离为$L$且该问题离散处理,显然复杂度为:$O(len(trips)) + O(L)$。
题目来源:力扣(LeetCode)相关链接:https://leetcode-cn.com/problems/car-pooling/solution/han-fen-xi-si-lu-de-shi-xing-dai-ma-by-jiachen_zha/