Minimum Work

Moderate
0/80
Average time to solve is 30m
profile
Contributed by
0 upvote

Problem statement

You are given ‘N’ tasks. The duration to complete the tasks is given by an array ‘TIMES’ of length ‘N’. You can choose to skip tasks but you cannot skip 3 tasks in a row.

To complete task ‘i’ for ‘i’ in range [0, N-1] takes TIMES[i] time.

Find the minimum time you need to invest to complete the tasks that you assign to yourself.

Example: 
Input: ‘N’ = 5,  ‘TIMES’ = [1, 2, 3, 1, 2]

Output: 2.

The optimal assignment of tasks is to choose the 0th and 3rd tasks. The duration of the 0th and 3rd tasks is [1, 1]. So the time required to complete the task is 1 + 1 = 2.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line will contain the integer 'T', denoting the number of test cases.

The first line of each test case contains an integer ‘N’ denoting the number of tasks.’. 

The second line of each test case contains ‘N’ space-separated integers denoting the duration of tasks.
Output format : 
For each test case, you don’t need to print anything just return the minimum time you need to complete the tasks that you assign to yourself.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 10^5
1 <= TIMES[ i ] <= 10^5

Sum of N Over all the Test cases <= 10^5

Time Limit: 1 sec
Sample Input 1 :
2
5
4 2 2 3 1
3
10 10 10
Sample Output 1 :
2
10
Explanation Of Sample Input 1 :
For the First case:
Skip the first two tasks then complete the 3rd task and then again skip the last two tasks. Hence the time required to complete the tasks is 10.


For the second case:
Complete the first task and then skip the last two tasks. Hence Hence the time required to complete the tasks is 2.
Sample Input 2 :
2
8
1 2 3 4 5 6 7 8
5
5 3 4 1 2
Sample Output 2 :
9
4
Hint

Can you think of a way to recursively generate all possible combinations of valid tasks and then find the minimum duration?

Approaches (3)
Recursion

In this approach, We can use recursion to generate all possible valid tasks assignment. Let us define a recursive function that depends on the parameters (current_task and last_task) where current_task denotes the task we are currently doing and the last_task denotes the last task that we did. 

Now for any task, we can either assign that task to ourselves or skip that task. We can skip that task only if the tasks skipped between the last task and the current task is not greater than 2. Let us modify the function parameters a little with new parameters as (the index of the current task (‘IDX’) and the count of the tasks skipped between the last tasks and current task(‘LAST’)). Now we can define the recurrence relation as:


 

If ‘LAST’ < 2:

F(IDX, LAST) = minimum of ( F(IDX+1, LAST + 1), ‘TIMES[ IDX ]’ + F(IDX+1, 0 ) ).

Else:

F(IDX, LAST) = ‘TIMES[ IDX ]’ + F(IDX+1, 0 ).


 

The steps are as follows:-

// Recursive function to get minimum time

function getMinWorkUtil( [ int ] times, int idx, int last):

  1. If the value of last is 3 then return 1e7.
  2. If the value of 'IDX' is greater or equal to 'N' then return  0.
  3. Recursively call the 'getMinWorkUtil' function by first taking the current work and then not taking the current work and then return the minimum of the values returned by them.


 

Function getMinWork( [ int ] times):

  1. Call the 'getMinWorkUtil' function and store the value returned in the 'ANS' variable.
  2. Return the value of the 'ANS' variable.
Time Complexity

O( 2^N ), Where ‘N’ is the number of the tasks.

 

For each task sometimes we have two choices, either do that task or skip it. We are recursively exploring all the possibilities. In the worst case, there will be at most 2 ^ ‘N’ possibilities.

Hence the time complexity is O( 2^N ).

Space Complexity

O( N ),  Where ‘N’ is the number of the tasks.

 

The height of the recursive tree will be at most ‘N’ so the space required for the recursion stack is O( N ).

Hence space complexity is O( N ).

Code Solution
(100% EXP penalty)
Minimum Work
Full screen
Console