1457. Minimum Difficulty of a Job Schedule
My accepted C++ solution to LeetCode problem 1457, Minimum Difficulty of a Job Schedule, running in 16ms.
- Difficulty: Hard
- C++
- Runtime 16ms
- Memory 11.1MB
- Updated
Read the problem on LeetCode View on GitHub
The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.
C++
Accepted on LeetCode — runtime 16ms, memory 11.1MB, accepted 2025-12-27.
class Solution {
public:
int minDifficulty(vector<int>& jobDifficulty, int d) {
int n = jobDifficulty.size();
if (n < d) return -1;
vector<vector<int>> dp(d + 1, vector<int>(n + 1, 1e9));
dp[0][0] = 0;
for (int day = 1; day <= d; day++) {
for (int i = day; i <= n; i++) {
int maxD = 0;
for (int j = i; j >= day; j--) {
maxD = max(maxD, jobDifficulty[j - 1]);
dp[day][i] = min(dp[day][i], dp[day - 1][j - 1] + maxD);
}
}
}
return dp[d][n];
}
};