Last Updated: 10 Jun, 2022
Max tasks in the given Budget
Moderate
Asked in company
You are given a straight line starting at 0 to 10^9. You start at zero, and there are ‘N’ tasks you can perform. ‘ith’ task is located at point 'Task[i][0]' in the line and requires 'Task[i][1]' time to be performed.
To perform the task, you need to reach the point 'Task[i][0]' and spend 'Task[i][1]' time at that location. e.g. (5,8) lies at five, so travel distance is five, and work effort is 8.
It takes one second to travel one unit of the path.
Now, we are given a total of ‘totalTime’ 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 ‘totalTime’.
For example:
3 tasks and 16 units of total time.
Task = [( 2, 8 ) , ( 4, 5) , ( 5, 1)]
( 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.
Skipping the first task leaves us enough time to complete the other two tasks. Going to the location of the third task and coming back costs 2x5 =10 sec, and performing tasks at locations 4 and 5 cost us 5+1 = 6 sec.
Total time spent will be 10+6=16 sec.
Input Format :
First-line contains 'T,' denoting the number of Test cases.
For each Test case:
The first line contains two integers, 'N' and ‘totalTime’, where ‘N’ is the number of tasks and ‘totalTime’ is the time given.
Next, the ‘N’ lines contain two integers, ‘Task[i][0]’ and ‘Task[i][1]’, each denoting the distance of the task and the time required to complete the task.
Output Format:-
After operating, you must return the maximum number of tasks you can finish in time ‘totalTime’.
Note:-
You don’t need to print anything. Just implement the given function.
Constraints :
1<= T <=10
1<= N <=10^5
1<= totalTime <=10^9
1<= Task[i][0] <= 10^9
1<= Task[i][1] <= 10^5
Time Limit: 1 sec
Approaches
Approach :
- For each task, we have two choices, either to perform it or not. So, we will recursively check for each possibility.
- For every task performed, subtract the time to complete the task from the available time. Also, maintain the count of tasks performed and the maximum distance we have to go for performing any task.
- Whenever we have completely traversed all the tasks, we have remaining time, count of tasks, and the maximum distance.
- For a valid sequence of operations, the remaining time must exceed ‘2*maximum distance’. For every valid sequence ‘answer’ is updated with the maximum of ‘answer’ and the count of tasks.
Algorithm:
- Initially answer = 0.
- Call “ recur ( curTask, n, completedTasks, task, remTime, maxDist, answer)”
- curTask - We are currently at this task
- n - Total number of tasks
- completedTasks - number of tasks we have performed till now
- task - Array of Tasks
- remTime - Time remaining with us.
- maxDist - Distance of the task which is farthest.
- answer - Stores our answer.
For every recursive call-
- If ‘curTask’ equals ‘n’, then we have finished processing all tasks. Hence, if we have enough time to reach the farthest task, i.e. “remTime >= 2 * maxDist “, we update the ‘answer’ with a maximum of ‘answer’ and ‘completedTasks’ and return.
- Else
- If we complete the current task,
recur (curTask+1, n,completedTasks+1,task,remTime-task[curtask][1], max( maxDist, task[curTask][0]), answer)
- Else we didn’t complete the current task,
recur (curTask+1, n,completedTasks,task,remTime,maxDist, answer)
Return ‘answer’
Approach :
- We will sort the task array according to the position.
- We will maintain a priority_queue that helps find the time taken by the tasks we have included in our answer.
- Now we will iterate through all the tasks.
- For the ‘ith’ task, we need a total of ‘2 * Task[i][0]’ time to go and come back from the ‘ith’ task. So, the remaining time will be ‘totalTime - 2 * Task[i][0] ‘.
- Now subtract ‘Task[i][1]’ from the ‘totalTime’ and push ‘-Task[i][1]’ in the queue.
totalTime = totalTime - ( 2 * Task[i][0] ) - Task[i][1].
- Take the top value from the queue and remove it from the queue and subtract it from the ‘totalTime’, until ‘totalTime’ is less than 0.
- The ‘answer’ is the maximum of the ‘answer’ and the current size of priority_queue.
- Now add ‘2 * Task[i][0]’ to ‘totalTime’ for the next iteration.
We will do this for all tasks, and the answer to the problem will be the maximum task we can perform among them.
Algorithm:
Sort the array of tasks.
Initialize an empty minimum priority_queue that will contain all the tasks we are performing currently.
For the ‘ith’ task in tasks :
- The time to go and come back from this task is ‘2*Task[i][0]’ and the time to complete the current task is ‘Task[i][1]’.
totalTime = totalTime - ( 2 * Task[i][0] ) - Task[i][1].
- Insert ‘-Task[i][1]’ to the priority_queue.
- While ‘totalTime’ < 0:
- Let ‘maxTask’ be the top value from the priority queue.
- Remove ‘maxTask’ from the queue and subtract it from the ‘totalTime’.
- The ‘answer’ is the maximum of the ‘answer’ and the current size of priority_queue.