javascript - 车道分配算法

Question

我有一个汽车对象数组(按开始升序排序)，表示如下:

var cars = [
  {"name": "car0blue", "start": 0, "end": 3},
  {"name": "car1red", "start": 1, "end": 4},
  {"name": "car2yellow", "start": 3, "end": 7},
  {"name": "car3green", "start": 3, "end": 6},
  {"name": "car4purple", "start": 4, "end": 7},
  {"name": "car5grey", "start": 5, "end": 11},
]

起点和终点描述了汽车在 x 轴上的位置。
我正在尝试将汽车分配到车道，始终努力将汽车放在编号最低的车道上，而不会撞到另一辆车。
这是我试图达到的结果

carsWithLanes = [
  {"name": "car0blue", "start": 0, "end": 3, "lane": 0},
  {"name": "car1red", "start": 1, "end": 4, "lane": 1},
  {"name": "car2yellow", "start": 3, "end": 7, "lane": 0},
  {"name": "car3green", "start": 3, "end": 6, "lane": 2},
  {"name": "car4purple", "start": 4, "end": 7, "lane": 1},
  {"name": "car5grey", "start": 5, "end": 11, "lane": 3},
]

这是逻辑
为了适应给定车道，起始值必须大于或等于给定车道中汽车的结束值。
“car0blue”:因为这是分配到车道 0 的第一辆车。

{"name": "car0blue", "start": 0, "end": 3, "lane": 0}

“car1red”:因为它不适合 0 号车道，所以它被分配到 1 号车道。

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},

“car2yellow”:因为它适合 0 号车道，所以它被分配到 0 号车道。

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},
{"name": "car2yellow", "start": 3, "end": 7, "lane":0},

“car3green”:因为它不适合车道 0 或车道 1，它被分配到车道 2。

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},
{"name": "car2yellow", "start": 3, "end": 7, "lane": 0},
{"name": "car3green", "start": 3, "end": 6, "lane": 2},

“car4purple”:因为它不适合 0 号车道，但可以适合 1 号车道，所以它被分配到 1 号车道。

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},
{"name": "car2yellow", "start": 3, "end": 7, "lane": 0},
{"name": "car3green", "start": 3, "end": 6, "lane": 2},
{"name": "car4purple", "start": 4, "end": 7, "lane": 1},

“car5grey”:因为它不适合车道 0、车道 1 或车道 2，它被分配到车道 3

{"name": "car0blue", "start": 0, "end": 3, "lane": 0},
{"name": "car1red", "start": 1, "end": 4, "lane": 1},
{"name": "car2yellow", "start": 3, "end": 7, "lane": 0},
{"name": "car3green", "start": 3, "end": 6, "lane": 2},
{"name": "car4purple", "start": 4, "end": 7, "lane": 1},
{"name": "car5grey", "start": 5, "end": 11, "lane": 3},

我试过的
我想我需要某种包含每个车道的当前结束值的数组来比较，但我意识到我被困住了，正在寻找一些帮助。

      var laneBuffer = [];

      cars.forEach((item, i) => {
        if (i === 0) {
          item.lane = 0;
          laneBuffer.push(item);
        }
        else{
          //Brain freeze...
          });
        }
      });

Answer 1

有趣的问题。该算法应该适用于所有情况。

const cars = [
    { name: "car0blue", start: 0, end: 3 },
    { name: "car1red", start: 1, end: 4 },
    { name: "car2yellow", start: 3, end: 7 },
    { name: "car3green", start: 3, end: 6 },
    { name: "car4purple", start: 4, end: 7 },
    { name: "car5grey", start: 5, end: 11 },
];

const lanes = [];
cars.forEach(placeInFreeLane);
console.log( cars );

// Algorithm:

function placeInFreeLane(car) {
    let lane = 0;
    while (!tryFitInLane(car, lane)) lane++;
    car.lane = lane;
}

function tryFitInLane(car, laneNumber) {
    const lane = lanes[laneNumber];
    if (lane === undefined) {
        lanes[laneNumber] = [car];
        return true;
    } else {
        const intersectsWithAny = lane.some(otherCar => intersects(car, otherCar));
        if (!intersectsWithAny) {
            lane.push(car);
            return true;
        }
    }
    return false;
}

function intersects(a, b) { return a.start < b.end && a.end > b.start; }

给定您的情况的输出(与所需的输出匹配):

[
  { "name": "car0blue", "start": 0, "end": 3, "lane": 0 },
  { "name": "car1red", "start": 1, "end": 4, "lane": 1 },
  { "name": "car2yellow", "start": 3, "end": 7, "lane": 0 },
  { "name": "car3green", "start": 3, "end": 6, "lane": 2 },
  { "name": "car4purple", "start": 4, "end": 7, "lane": 1 },
  { "name": "car5grey", "start": 5, "end": 11, "lane": 3 }
]

编辑:有趣的是，这里是另一个以更实用的方式编写的版本。这个是自包含的，不会改变原始或全局状态。它复制输入数据并且没有副作用。

// Algorithm:

const intersects = (a, b) => a.start < b.end && a.end > b.start;
const hasNoIntersectionsWith = (car) => (lane) => !lane.some((other) => intersects(car, other));
const getPacked = (cars) => {
    const lanes = [];
    return cars.map((car) => {
        let freeLaneIndex = lanes.findIndex(hasNoIntersectionsWith(car));
        if (freeLaneIndex < 0) freeLaneIndex = lanes.push([]) - 1;
        lanes[freeLaneIndex].push(car);
        return { ...car, lane: freeLaneIndex };
    });
};

// Example:

var cars = [
    { name: "car0blue", start: 0, end: 3 },
    { name: "car1red", start: 1, end: 4 },
    { name: "car2yellow", start: 3, end: 7 },
    { name: "car3green", start: 3, end: 6 },
    { name: "car4purple", start: 4, end: 7 },
    { name: "car5grey", start: 5, end: 11 },
];

console.log(getPacked(cars));