Car lane assignment algorithm
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));