车队问题

下面是2020年9月23日面试遇到的一道真实面试题。面试官选题自LeetCode853. 车队。

题目

截图自LeetCode853. 车队

分析解题思路

首先，对问题进行抽象，如下图的建模，target长的公路被按照单位距离划分，所有的在路上的车就对应着数轴上的一点。例如示例中，target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]，长度12的线段被分为12等分，并且公路上的五辆车已经在数轴上标识。

抽象的数据模型

分析问题：

• 如何判断后车可以追上前车？当后车到达终点的时间短于前车时，表明可以追上；
• 如果后车追上前车，两辆车合并为一个车队，之后以速度更慢的前车速度继续行驶。在图中抽象为当后车追上前车之后，图中只保留前车即可；
• 初始时我们认为路上共有N个车队，当后车追上前车，两车合并为一个车队时，路上的车队数量减去1；
• 从数轴左边起，后车依次去与前车到达时间比较，如果能追赶上，那么合并为一个车队。之后遍历到这个合并的车队时，再拿其与前车比较，如果能追上继续合并。直到遍历了所有车辆为止。

算法执行示例，过程如下面图中所示：

1. 第一行，指针指向位置0的车，追不上任何的前车；
2. 第二行，指针移动，指向位置3的车，追上了位置5的车，两车合并一个车队；
3. 第三行，继续移动指针，指向位置5的车，追不上任何的前车；
4. 第四行，继续移动指针，指向位置8的车，追上位置10的车，两车合并一个车队；
5. 第五行，指针移动停止，位置10的车为最前的车，不需要追赶其他车。

算法执行过程

代码

具体细节已经在代码中注释。这里关于排序使用的是JDK自带的排序方法Arrays.sort()。如果自己编写可以考虑快速排序，比较Car对象中字段position的大小确定顺序。

private class Car{
    int position;
    double timeToDestination;
}

public int carFleet(int target, int[] position, int[] speed) {
    final int N = position.length;
    if (N != speed.length){
        return -1;
    }
    //position和speed构建Car数组
    Car[] cars = new Car[N];
    for (int i = 0; i < N; ++i){
        Car c = new Car();
        c.position = position[i];
        c.timeToDestination = (double)(target - position[i])/speed[i];
        cars[i] = c;
    }
    //升序排序Car数组，也就是下标0是离终点最远的车(后车)，下标N-1是离终点最近的车(前车)
    Arrays.sort(cars, Comparator.comparingInt(a -> a.position));

    //初始化车队有N个
    int result = N;

    //遍历Car数组，后车去追前车
    //当后车到达终点的时间短于前车时，表明可以追上
    //如果追上，合并为一个车队，以速度更慢的前车速度继续行驶
    for (int i = 0; i < N - 1; ++i){
        for (int j = i + 1; j < N; ++j){
            if (cars[i].timeToDestination <= cars[j].timeToDestination){
                result--;
                break;
            }
        }
    }
    return result;
}