javascript - 车道分配算法

我有一系列汽车对象(按开始顺序升序排列)，表示如下:

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”:由于它不适合 channel 0，但适合 channel 1，因此将其分配给 channel 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},

我尝试过的内容
我想我需要一种包含每个 channel 的当前最终值的数组来进行比较，但意识到我被困住了并寻求帮助。

      var laneBuffer = [];

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

最佳答案

好玩的问题。该算法应在所有情况下均有效。

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));

关于javascript - 车道分配算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/65708618/