1
$\begingroup$

Consider the following setup:

Input: An array of tasks $T=[t_1,t_2,...,t_k]$ where each task $t_i$ is an object that has the following features: start time $s,$ finish time $f$ and coordinates $x$ and $y$, which give the location where the task needs to be performed. Next, we have an array of people $P=[p_1,p_2,...,p_m]$ where each person $p_i$ is an object which initially starts at the origin, i.e. $p_i.x =p_i.y=0.$ Consider the function assign which assigns positions every $10$ minutes to each person of the array $P$ based on the new task array $T$ recieved. Note that every 10 minutes we receive a new array $T$ containing tasks that must be assigned. Furthermore, each person moves at a speed $v$ km/hr to the assigned position.

The goal is to assign as many tasks as possible. What possible algorithms should I look for in order to solve this problem?

$\endgroup$
  • $\begingroup$ This looks like an interesting question. "The goal is to assign as many tasks as possible." May I just assign every person to all the tasks? You have not specified what a successful assignment of a person to one task means. If a person is assigned a task, is he supposed to move to where the task is? That looks like what you mean, but I cannot be sure. Can a person accomplish two tasks within one 10 minutes? Can you provide some trivial and some non-trivial examples? Do you have an original source that you can credit to? $\endgroup$ – Apass.Jack Sep 18 '18 at 6:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.