Minimum time to finish tasks without skipping two consecutive - GeeksforGeeks

Minimum time to finish tasks without skipping two consecutive - GeeksforGeeks
Given time taken by n tasks. Find the minimum time needed to finish the tasks such that skipping of tasks is allowed, but can not skip two consecutive tasks.

Let minTime(i) be minimum time to finish till i’th task. It can be written as minimum of two values.

1. Minimum time if i’th task is included in list, let this time be incl(i)
2. Minimum time if i’th task is excluded from result, let this time be excl(i)

incl(i) can be written as below.

// There are two possibilities
// (a) Previous task is also included
// (b) Previous task is not included
incl(i) = min(incl(i-1), excl(i-1)) +
              arr[i] // Since this is inclusive 
                     // arr[i] must be included 

excl(i) can be written as below.

// There is only one possibility (Previous task must be
// included as we can't skip consecutive tasks.
excl(i) = incl(i-1)  

A simple solution is to make two tables incl[] and excl[] to store times for tasks. Finally return minimum of incl[n-1] and excl[n-1]. This solution requires O(n) time and O(n) space.

If we take a closer look, we can notice that we only need incl and excl of previous job. So we can save space and solve the problem in O(n) time and O(1) space. Below is C++ implementation of the idea.

int minTime(int arr[], int n)

{

    // Corner Cases

    if (n <= 0)

        return 0;

 

    // Initialize value for the case when there

    // is only one task in task list.

    int incl = arr[0];  // First task is included

    int excl = 0;       // First task is exluded

 

    // Process remaining n-1 tasks

    for (int i=1; i<n; i++)

    {

       // Time taken if current task is included

       // There are two possibilities

       // (a) Previous task is also included

       // (b) Previous task is not included

       int incl_new = arr[i] + min(excl, incl);

 

       // Time taken when current task is not

       // included.  There is only one possibility

       // that previous task is also included.

       int excl_new = incl;

 

       // Update incl and excl for next iteration

       incl = incl_new;

       excl = excl_new;

    }

 

    // Return maximum of two values for last task

    return min(incl, excl);

}

Find minimum time to finish all jobs with given constraints
Maximum sum such that no two elements are adjacent.

Read full article from Minimum time to finish tasks without skipping two consecutive - GeeksforGeeks