diff options
Diffstat (limited to 'other/min_difficulty_schedule.cpp')
-rw-r--r-- | other/min_difficulty_schedule.cpp | 36 |
1 files changed, 36 insertions, 0 deletions
diff --git a/other/min_difficulty_schedule.cpp b/other/min_difficulty_schedule.cpp new file mode 100644 index 0000000..40fab6e --- /dev/null +++ b/other/min_difficulty_schedule.cpp @@ -0,0 +1,36 @@ +#include "leetcode.h" +#include <algorithm> +#include <vector> + +class Solution { +public: + int minDifficulty(vector<int> &jobDifficulty, int d) { + int n = jobDifficulty.size(); + if (n < d) + return -1; + vector<int> dp(n, 1000), dp2(n), stack; + for (int i = 0; i < d; ++i) { + stack.clear(); + for (int j = i; j < n; j++) { + dp2[j] = j ? dp[j - 1] + jobDifficulty[j] : jobDifficulty[j]; + while (stack.size() && + jobDifficulty[stack.back()] <= jobDifficulty[j]) { + int k = stack.back(); + stack.pop_back(); + dp[j] = min(dp2[j], dp2[k] - jobDifficulty[k] + jobDifficulty[j]); + } + if (stack.size()) + dp2[j] = min(dp2[j], dp2[stack.back()]); + stack.push_back(j); + } + swap(dp, dp2); + } + return dp[n - 1]; + } +}; + +int main() { + Solution obj; + vector<int> jobDifficulty = {6, 5, 4, 3, 2, 1}; + cout << obj.minDifficulty(jobDifficulty, 2); +} |