我想创建一个碰撞事件的时间线，其中事件代表要处理的一定量的公斤，并且时间线每小时具有一定的容量。事件有一个静态的开始时间，但结束时间是根据要处理的权重和时间线的容量计算的。
我尝试计算延迟时间（以小时为单位），但它没有得到我期望的输出。
const kgPerHourSpeed = 1000;
const events = [
{ startDateTime: '2024-01-01T09:00:00.000Z', endDateTime: null, overlappingDelayHours: 0, kg: 1000 },
{ startDateTime: '2024-01-01T09:00:00.000Z', endDateTime: null, overlappingDelayHours: 0, kg: 1000 },
{ startDateTime: '2024-01-01T10:00:00.000Z', endDateTime: null, overlappingDelayHours: 0, kg: 1000 },
];
const calculateEndDateTime = (startDateTime, kg) => {
const hours = kg / kgPerHourSpeed;
const start = new Date(startDateTime);
start.setHours(start.getHours() + hours);
console.log(start);
return start;
}
// Iterate through events to calculate overlappingDelayHours
for (let i = 0; i < events.length; i++) {
const event1 = events[i];
endDateTime1 = calculateEndDateTime(event1.startDateTime, event1.kg);
events[i].endDateTime = endDateTime1.toISOString();
for (let j = i + 1; j < events.length; j++) {
const event2 = events[j];
const endDateTime2 = calculateEndDateTime(event2.startDateTime, event2.kg);
const startDateTime2 = new Date(event2.startDateTime);
// If event2 starts before event1 ends, they overlap
if (startDateTime2 < endDateTime1) {
const overlappingDuration = endDateTime1 - startDateTime2;
const overlappingDelayHours = overlappingDuration / (1000 * 60 * 60);
events[i].overlappingDelayHours += overlappingDelayHours;
events[j].overlappingDelayHours += overlappingDelayHours;
}
}
}
console.log(events);
输出：它会导致错误的输出，因为当包括延迟时，第三个事件也必须发生碰撞
0: {startDateTime: '2024-01-01T09:00:00.000Z', endDateTime: '2024-01-01T10:00:00.000Z', overlappingDelayHours: 1, kg: 1000}
1: {startDateTime: '2024-01-01T09:00:00.000Z', endDateTime: '2024-01-01T10:00:00.000Z', overlappingDelayHours: 1, kg: 1000}
2: {startDateTime: '2024-01-01T10:00:00.000Z', endDateTime: '2024-01-01T11:00:00.000Z', overlappingDelayHours: 0, kg: 1000}
预期输出：
0: {startDateTime: '2024-01-01T09:00:00.000Z', endDateTime: '2024-01-01T10:00:00.000Z', overlappingDelayHours: 3, kg: 1000}
1: {startDateTime: '2024-01-01T09:00:00.000Z', endDateTime: '2024-01-01T10:00:00.000Z', overlappingDelayHours: 3, kg: 1000}
2: {startDateTime: '2024-01-01T10:00:00.000Z', endDateTime: '2024-01-01T11:00:00.000Z', overlappingDelayHours: 2, kg: 1000}
如何用 JavaScript（或者类似的语言，如果您愿意的话）编写算法来根据每个事件的权重和时间线容量来计算完成它需要多长时间？如果物品发生碰撞，它们应该共享重叠时间内的每小时容量。非常感谢任何有关如何解决此问题的指导。
正如 Scott Sauyet 所建议的，这些活动平均分配容量。使用与 Scott Sauyet 相同的测试数据制成。它修改了原始数组和事件，但很容易复制原始数据。
const solution = (events, capacity) => {
events.sort((a, b) => a.startTime - b.startTime);
events.forEach(e => e.remaining = e.kg);
const currentEvents = new Set;
let nextIdx = 0;
let currentTime;
while (nextIdx < events.length) {
if (!currentEvents.size) {
const next = events[nextIdx++];
currentEvents.add(next);
currentTime = next.startTime;
}
let next = events[nextIdx];
while (currentEvents.size) {
const perEvent = capacity / 60 / currentEvents.size;
let shortest = next ? next.startTime - currentTime : Infinity;
currentEvents.forEach(e => {
const remainingTime = e.remaining / perEvent;
if (remainingTime < shortest) shortest = remainingTime;
});
currentEvents.forEach(e => {
e.remaining -= perEvent * shortest;
if (!e.remaining) {
delete e.remaining;
e.endTime = currentTime + shortest;
currentEvents.delete(e);
}
});
if (next?.startTime - currentTime === shortest) {
currentEvents.add(events[nextIdx++]);
next = events[nextIdx];
}
currentTime += shortest;
}
}
return events;
};
console.log(solution ( [
{id: 'a', kg: 8, startTime: 1},
{id: 'b', kg: 40, startTime: 5},
{id: 'c', kg: 12, startTime: 9},
{id: 'd', kg: 20, startTime: 16},
{id: 'e', kg: 4, startTime: 17},
{id: 'f', kg: 12, startTime: 27}
], 240))和基准
` Chrome/122
---------------------------------------------------------------
> n=6 | n=60 | n=600
Alexander 1.00x x100k 155 | 1.00x x10k 104 | 1.00x x1k 107
Scott Sauyet 3.11x x100k 482 | 6.32x x10k 657 | 38.41x x100 411
---------------------------------------------------------------
https://github.com/silentmantra/benchmark `
let chunkId = -99;
const $chunks = [1, 10, 100];
const $chunk = () => {
chunkId += 100;
return [
{ id: 'a', kg: 8, startTime: 1 * chunkId },
{ id: 'b', kg: 40, startTime: 5 * chunkId },
{ id: 'c', kg: 12, startTime: 9 * chunkId },
{ id: 'd', kg: 20, startTime: 16 * chunkId },
{ id: 'e', kg: 4, startTime: 17 * chunkId },
{ id: 'f', kg: 12, startTime: 27 * chunkId }
];
};
const $input = [];
// Helper function for sorting
const byStart = (a, b) => a.startTime - b.startTime
// Main (recursive) function
// capacity: total capacity
// evennts: {id, kg: load, startTime: minutes since beginning}
// time: minutes since start
// open: events that have started but not completed, inlude `remaining` field
// closed: events that have finished, now with `endTime` as well
const process = (capacity, events, time, open, closed) => {
// return the (sorted) closed events when completed
if (events.length == 0 && open.length == 0)
return closed.sort(byStart);
// how much of the capacity each event gets -- possibly too naive
const capacityShare = capacity / 60 / (open.length || 1)
// how long this runs before the next event starts or a running one finishes (minutes)
const interval = Math.min(
(events[0] || { startTime: Infinity }).startTime - time,
...open.map(({ remaining }) => remaining / capacityShare)
)
// how much of each running event is processed during this interval
const perEvent = capacityShare * interval
// the events that are closed at the end of this interval
const newClosed = open
.filter(({ remaining }) => remaining <= perEvent)
.map(({ remaining, ...rest }) => ({ ...rest, endTime: time + interval }))
// the remaining open events after we close the completed ones, with updated remaining kgs
const newOpen = open
.filter(({ remaining }) => remaining > perEvent)
.map(({ remaining, ...rest }) => ({ ...rest, remaining: remaining - perEvent }))
// the queued events that are opened for the next interval
const startingEvents = events
.filter(({ startTime }) => startTime == time + interval)
.map(e => ({ ...e, remaining: e.kg }))
// the remaining queued events after opening the approriate ones
const queuedEvents = events
.filter(({ startTime }) => startTime != time + interval)
// recur using these newly calculated values
return process(
capacity,
queuedEvents,
time + interval,
[...newOpen, ...startingEvents],
[...closed, ...newClosed]
)
}
// public function, just wraps `process`
const solution = (capacity, events) =>
process(capacity, [...events].sort(byStart), 0, [], [])
const solution3 = (events, capacity) => {
events.sort((a, b) => a.startTime - b.startTime);
events.forEach(e => e.remaining = e.kg);
const currentEvents = new Set;
let nextIdx = 0;
let currentTime;
while (nextIdx < events.length) {
if (!currentEvents.size) {
const next = events[nextIdx++];
currentEvents.add(next);
currentTime = next.startTime;
}
let next = events[nextIdx];
while (currentEvents.size) {
const perEvent = capacity / 60 / currentEvents.size;
let shortest = next ? next.startTime - currentTime : Infinity;
currentEvents.forEach(e => {
const remainingTime = e.remaining / perEvent;
if (remainingTime < shortest) shortest = remainingTime;
});
currentEvents.forEach(e => {
e.remaining -= perEvent * shortest;
if (!e.remaining) {
delete e.remaining;
e.endTime = currentTime + shortest;
currentEvents.delete(e);
}
});
if (next?.startTime - currentTime === shortest) {
currentEvents.add(events[nextIdx++]);
next = events[nextIdx];
}
currentTime += shortest;
}
}
return events;
}
// @benchmark TEST
solution(240, $input)
//@benchmark Alexander
solution3($input, 240);
/*@end*/eval(atob('e2xldCBlPWRvY3VtZW50LmJvZHkucXVlcnlTZWxlY3Rvcigic2NyaXB0Iik7aWYoIWUubWF0Y2hlcygiW2JlbmNobWFya10iKSl7bGV0IHQ9ZG9jdW1lbnQuY3JlYXRlRWxlbWVudCgic2NyaXB0Iik7dC5zcmM9Imh0dHBzOi8vY2RuLmpzZGVsaXZyLm5ldC9naC9zaWxlbnRtYW50cmEvYmVuY2htYXJrL2xvYWRlci5qcyIsdC5kZWZlcj0hMCxkb2N1bWVudC5oZWFkLmFwcGVuZENoaWxkKHQpfX0='));