Car lane assignment algorithm

Question

I have an array of car objects (sorted in ascending order by start) expressed as follows:

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},
]

The start and end describes where the cars are located on an x-axis.

I'm trying to assign the cars to lanes, always striving to put the car in the lowest numbered lane possible without bumping into another car.

This is the result I'm trying to achive

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},
]

This is the logic

To fit into a given lane the start value has to be greater than or equal to the end value of the car in the given lane.

"car0blue": since this is the first car it is assigned to lane 0.

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

"car1red": since it won't fit into lane 0 it's assigned to lane 1.

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

"car2yellow": since it will fit into lane 0 it's assigned to lane 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": since it won't fit into lane 0 or lane 1 it's assigned to lane 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": since it won't fit into lane 0 but will fit into lane 1 it's assigned to lane 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": since it won't fit into lane 0, lane 1 or lane 2 it's assigned to lane 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},

What I've tried

I figured I would need some sort of array containing the current end values of each lane to compare against but realize I'm stuck and looking for some help.

      var laneBuffer = [];

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

Answer 1

Fun problem. This algorithm should work in all cases.

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

Output given your case (matches the desired output):

[
  { "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 }
]

---

EDIT: for the fun of it here is another version written in a more functional manner. This one is self contained and doesn't mutate the original or global state. It copies the input data and has no side effects.

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

Answer 2

You need to check each lane if the last end is smaller or equal to the current car start.

If you find a lane then you can add the car, if not you create a new lane.

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},
]

const carLanes = [];

cars.forEach(car=>{
  const availableLane = carLanes.find(lane=>
    lane[lane.length-1].end <= car.start
  );
  if (availableLane) {
    availableLane.push(car);
  } else {
    carLanes.push([car]);
  }
})

console.log(carLanes);