algorithm - 设计算法以找到完成订单交付的最小交付代理

Question

我有以下数据集，其中 pickedUp 和 deliveredAt 是标准化时间戳:

const orders = [{
    pickedUp: 100, // Needed - 1, AgentID - 1
    deliveredAt: 102
}, {
    pickedUp: 100, // Needed - 2, AgentID - 2
    deliveredAt: 110
}, {
    pickedUp: 200, // Needed - 2, AgentID - 2
    deliveredAt: 220,
}, {
    pickedUp: 200, // Needed - 2, AgentID - 1
    deliveredAt: 400
}, {
    pickedUp: 105, // Needed - 2, AgentID - 1
    deliveredAt: 180
}];

现在，从评论中可以看出，至少需要 2 个代理来交付所有这些订单。

但是，在我的实现中，对于上述数据集，我收到的最小值为 4。

这是我的实现:

const orders = [{
  pickedUp: 100, // Needed - 1, AgentID - 1
  deliveredAt: 102
}, {
  pickedUp: 100, // Needed - 2, AgentID - 2
  deliveredAt: 110
}, {
  pickedUp: 200, // Needed - 2, AgentID - 2
  deliveredAt: 220,
}, {
  pickedUp: 200, // Needed - 2, AgentID - 1
  deliveredAt: 400
}, {
  pickedUp: 105, // Needed - 2, AgentID - 1
  deliveredAt: 180
}];

function findMinumumDeliveryAgents(input) {
  let needed = 1;
  // sort by pickup time
  let sorted = input.sort((a, b) => {
    return a.pickedUp - b.pickedUp
  })
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i].pickedUp < sorted[i - 1].deliveredAt) {
      needed++;
    }
  }
  return needed
}

console.log(findMinumumDeliveryAgents(orders));

出现差异是因为带有 pickedUp: 105 的订单与 AgentID - 2 匹配，而不是 AgentID - 1。

知道如何有效地解决这个问题吗？

Answer 1

您跟踪的是重叠间隔的数量，而不是代理的数量。您的实现的错误之处在于，当释放 AgentID=1 的代理时，您必须跟踪您可以使用 pickedUp 将他重新分配到数据点: 105。

我的实现如下:

const orders = [{
  pickedUp: 100, // Needed - 1, AgentID - 1
  deliveredAt: 102
}, {
  pickedUp: 100, // Needed - 2, AgentID - 2
  deliveredAt: 110
}, {
  pickedUp: 200, // Needed - 2, AgentID - 2
  deliveredAt: 220,
}, {
  pickedUp: 200, // Needed - 2, AgentID - 1
  deliveredAt: 400
}, {
  pickedUp: 105, // Needed - 3, AgentID - 1
  deliveredAt: 180
}];

function findMinumumDeliveryAgents(input) {
  let needed = 1, has = 1; // sort by pickup time
  let sorted = input.sort((a, b) => {
    return a.pickedUp - b.pickedUp
  })
  for (let i = 1; i < sorted.length; i++) {
    if (sorted[i].pickedUp < sorted[i - 1].deliveredAt) {
      if (has === 0) {
        needed++;
      } else {
        has--;
      }
    } else if (has < needed) {
        has++;
    }
 }
  return needed
}

console.log(findMinumumDeliveryAgents(orders));

我从 has = 0 开始，在这种情况下，b/c has = 1 的初始化将导致无法解释第三个代理。