<p>You want to schedule a list of jobs in <code>d</code> days. Jobs are dependent (i.e To work on the <code>i<sup>th</sup></code> job, you have to finish all the jobs <code>j</code> where <code>0 &lt;= j &lt; i</code>).</p>

<p>You have to finish <strong>at least</strong> one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the <code>d</code> days. The difficulty of a day is the maximum difficulty of a job done on that day.</p>

<p>You are given an integer array <code>jobDifficulty</code> and an integer <code>d</code>. The difficulty of the <code>i<sup>th</sup></code> job is <code>jobDifficulty[i]</code>.</p>

<p>Return <em>the minimum difficulty of a job schedule</em>. If you cannot find a schedule for the jobs return <code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2020/01/16/untitled.png" style="width: 365px; height: 370px;" />
<pre>
<strong>Input:</strong> jobDifficulty = [6,5,4,3,2,1], d = 2
<strong>Output:</strong> 7
<strong>Explanation:</strong> First day you can finish the first 5 jobs, total difficulty = 6.
Second day you can finish the last job, total difficulty = 1.
The difficulty of the schedule = 6 + 1 = 7 
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> jobDifficulty = [9,9,9], d = 4
<strong>Output:</strong> -1
<strong>Explanation:</strong> If you finish a job per day you will still have a free day. you cannot find a schedule for the given jobs.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> jobDifficulty = [1,1,1], d = 3
<strong>Output:</strong> 3
<strong>Explanation:</strong> The schedule is one job per day. total difficulty will be 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= jobDifficulty.length &lt;= 300</code></li>
	<li><code>0 &lt;= jobDifficulty[i] &lt;= 1000</code></li>
	<li><code>1 &lt;= d &lt;= 10</code></li>
</ul>

class Solution {
public:
    int minDifficulty(vector<int>& jobDifficulty, int d) 
    {
        int jobs = jobDifficulty.size();

        if(jobs < d) return -1;
        if(jobs == d) return accumulate(jobDifficulty.begin(), jobDifficulty.end(), 0);

        int max_difficulty = *max_element(jobDifficulty.begin(), jobDifficulty.end()) + 1;

        // Initialize vectors to store difficulty for previous and current days
        vector<int> prv_day(jobs, max_difficulty), curr_day(jobs);

        // Iterate over each day
        for (int days = 0; days < d; ++days) 
        {
            vector<int> stack;

            // Iterate over each job starting from the current day
            for (int i = days; i < jobs; i++) 
            {
                // Calculate difficulty for the current day
                if (i > 0)
                    curr_day[i] = prv_day[i - 1] + jobDifficulty[i];
                else 
                    curr_day[i] = jobDifficulty[i];
                // Start fresh day with the first job as ith

                // Handle job dependencies and find minimum difficulty
                while (!stack.empty() && jobDifficulty[stack.back()] <= jobDifficulty[i]) {
                    int j = stack.back(); 
                    stack.pop_back();
                    curr_day[i] = min(curr_day[i], curr_day[j] - jobDifficulty[j] + jobDifficulty[i]);
                }
                
                // Update difficulty based on previous days
                if (!stack.empty()) {
                    curr_day[i] = min(curr_day[i], curr_day[stack.back()]);
                }

                // Add the current job to the stack
                stack.push_back(i);
            }

            // Update difficulty vectors for the next day
            swap(prv_day, curr_day);
        }

        // Return the minimum difficulty for the last day
        return prv_day[jobs - 1];
    }
};
9700