Design Algorithm to find minimum delivery agents to complete delivery of orders

Question

I have the following dataset, where pickedUp and deliveredAt are normalized timestamps:

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

Now, as seem from the comments, a minimum of 2 agents are needed to deliver all these orders.

However, in my implementation, for the above dataset, I receive 4 as the minimum.

Here is my implementation:

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

The discrepancy occurs because the order with pickedUp: 105 is matched with AgentID - 2, and not AgentID - 1.

Any idea how to solve this problem efficiently?

shouldn't answer be 2 ... worker 1 will do jobs 1, 3, 5 and worker 2 will do 2 and 4 ... am I missing something? — รยקคгรђשค, Sep 02 '19 at 11:10
Possible duplicate of [Scheduling Jobs/Intervals in a minimum number of slots](https://stackoverflow.com/questions/34776638/scheduling-jobs-intervals-in-a-minimum-number-of-slots) — user202729, Sep 02 '19 at 11:19
Have a look at this .. https://algorithmsandme.com/interval-partitioning-problem/ — รยקคгรђשค, Sep 02 '19 at 12:02

Hari Amoor · Answer 1 · 2019-09-03T01:45:21.357

You're keeping track of the number of overlapping intervals, not the number of agents. What is amiss with your implementation is the logic that, when the agent with AgentID=1 is freed up, you have to keep track of that you can reassign him to the data point with pickedUp: 105.

My implementation of this is as follows:

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

I start with has = 0 in this case b/c an initialization of has = 1 would result in a failure to account for the third agent.

There was a mistake in the question - minimum needed is actually `2` not `3`. Apologies — Ayush Gupta, Sep 02 '19 at 11:19

Design Algorithm to find minimum delivery agents to complete delivery of orders

1 Answers1