Minimize Time

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
0 upvote
Asked in company
D.E.Shaw

Problem statement

Ninja wants to go on a vacation in his summer holidays. But he got a lot of homework from his school which requires a certain amount of time to complete. As the ninja was the topper of the class he was allowed to skip tasks, but cannot skip two consecutive tasks from his homework. You are given an array, ‘ARR’ of ‘N’ integers. Find the minimum time ninja needs to spend to complete the homework.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of the input contains a single integer 'T', representing the number of test cases.

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

The second line of each test case contains ‘N’ space-separated integers, representing the time needed to complete each task.
Output Format : 
For each test case, print the minimum time needed to complete the homework.

Print the output of each test case in a separate line.
Note : 
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 10
1 <= N <= 5*10^3

Time Limit : 1 sec
Sample Input 1 :
2
4
10 5 7 10
2
10 30
Sample Output 1 :
12
10
Explanation For Sample Input 1 :
For the first test case :

We can skip the first and the last tasks to complete the homework in 12 units of time.

For the second test :

We can skip the last task to complete the homework in 10 units of time.
Sample Input 2 :
2
8
10 5 2 4 8 6 7 10
4
1 2 3 4
Sample Output 2 :
22
4
Hint

Try to check time if we include the ‘ith’ task or exclude it.

Approaches (2)
Greedy Approach

For any ‘ith’ task we have two choices with us whether to include the ‘ith’ task or exclude the ‘ith’ task.

 

  1. If we include the ‘ith’ task, we again have two choices with us whether to include the previous task or not.
  2. If we exclude the ‘ith’ task we only have one choice by choosing the previous task as we are not allowed to skip two consecutive tasks.

We can maintain an array to keep track of time.

 

Here is the algorithm :
 

  1. Base case
    • If ‘N’ is smaller than equal to 0, return 0.
  2. Create an array (say, ‘INC’) of size ‘N’ that will store the time of including the tasks and initialize ‘INC[0]’ with ‘ARR[0]’.
  3. Create an array (say, ‘EXC’) of size ‘N’ that will store the time of excluding the tasks and initialize ‘EXC[0]’ with 0.
  4. Run a loop from 1 to ‘N’  (say, iterator ’i’) to traverse each task.
    • Update ‘INC[i]’ (include the current task) with the sum of ‘ARR[i]’ and a minimum of ‘EXC[i - 1]’ and ‘INC[i - 1]’
    • Update ‘EXC[i]’ (exclude the current task) with the ‘INC[i - 1]’.
  5. Finally, return the minimum of ‘INC[N - 1]’ and ‘EXC[N - 1]’.
Time Complexity

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

 

We traverse all the tasks once to find the time’. Therefore, the overall time complexity will be O(N).

Space Complexity

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

 

We use two extra arrays to maintain the time of including and excluding the tasks. Therefore, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Minimize Time
Full screen
Console