Max Tasks that can be completed in given time

user_13383627 0
Viewed 2975

I recently came across a this question in a forum: You are given a straight line starting at 0 to 10^9. You start at zero and there are n tasks you can perform. i th task is located at point i in the line and requires 't' time to be performed. To perform the task you need to reach the point i and spend 't' time at that location.

example: (5,8) lies at 5 so travel distance is 5 and work effort is 8. Total effort is calculated as travel distance + time required to complete the work. It takes one sec to travel one unit of path.

Now we are given total T seconds and we need to complete as many tasks as possible and reach back to starting position Find the max number of tasks that you can finish in time T.

example :

3 16 - 3 tasks and 16 units of total time

2 8 - task 1 at position 2 in line and takes 8 sec to complete

4 5 - task 2 at position 4 in line and takes 5 sec to complete

5 1 - task 3 at position 5 in line and takes 1 sec to complete

​​​​​​​ Output : 2

Explanation : If we take task 1 at location 2 which requires 8 sec then getting to location 2 takes 2s and completing the task takes 8s leaving us with only 6s which is not enough for completing other task

On the other hand skipping the fist task leaves us enough time to complete the other two tasks.

Going to location and coming back costs 2x5 =10s and performing task at location 4 and 5 cost us 5+1 = 6s. Total time spent will be 10s+6s=16s.

I am new to graphs and DP so I was not sure which approach to use Hamiltonian cycle, Knapsack or Longest Path. Can someone please help me with the most efficient approach to solve this.

dynamic-programming graph data-structures time-complexity algorithm
2 Answers

Let's iterate from the first task to the last, according to distance. As we go, it's clear that after subtracting 2 * distance(i) + effort(i) for considering the current task as our last, the most tasks we can achieve can be found by greedily accumulating as many earlier tasks as possible into the remaining time, ordering them by increasing effort.

Therefore, an efficient solution could insert the seen element into a data-structure ordered by effort, dynamically updating the best solution so far. (I originally thought of using a treap and binary search but j_random_hacker suggested a much simpler way in the comments below this answer.)

user_20347870

Suggestion:

For each task n create a graph like this

enter image description here

Join up these graphs for all the tasks.

enter image description here

Run a travelling salesman algorithm to find the minimum time to do all the tasks ( = visit all the nodes in combined graph )

Remove tasks in an orderly sequence. This will give you a collection of results for different numbers of tasks performed. Choose the one that does the most number of tasks that still remains under the time limit.

Since you are maximizing the number of tasks performed, start by removing the longest tasks so that you will be left with lots of short tasks.

user_165820
Related