Max tasks in the given Budget

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
1 upvote
Asked in company
PayPal

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
4 11
2 3
3 5
1 4
6 1
4 20
1 1
2 1
3 1
4 1
Sample Output 1 :
2
4
Explanation Of Sample Input 1 :
For testcase one:
Task= [ (2,3), (3,5), (1,4), (6,1)]    , totalTime= 11
In this case, we can go to position two and complete tasks one and three. This can be done in 2 * 2 + (3 + 4) =  11 sec.
Hence, the answer to this test case will be 11.
For test case two:
Task= [ (1,1), (2,1), (3,1), (4,1)]    , totalTime= 20
In this case, we can go to position four and complete tasks one, two, three, and four. This can be done in 2 * 4 + (1+1+1+1) = 12 sec.
Hence, the answer to this test case will be 4.
Sample Input 2 :
2
3 40 
6 5
5 5
3 7
1 10
10 1
Sample Output 2 :
3
0
Hint

For any distance ‘Task[i][0]’ try to complete tasks till Task[i][0], which takes less time first.

Approaches (2)
Brute Force

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’

Time Complexity

O( 2 ^ N ). Where ‘N’ is the size of the array. 

We are iterating over the size ‘N’ task array and for every task, we have two choices. 

Hence, the overall complexity will be O( 2^N ).

Space Complexity

O(N), where ‘N’ is the size of the array. 

We have to store the tasks. 

So, the Space Complexity is O(N).

Code Solution
(100% EXP penalty)
Max tasks in the given Budget
Full screen
Console