1335. Minimum Difficulty of a Job Schedule
Вы хотите составить расписание списка заданий на d дней. Задания зависят друг от друга (т.е. чтобы выполнить задание i, вы должны закончить все задания j, где 0 <= j < i).
Вы должны выполнять как минимум одно задание каждый день. Сложность расписания заданий — это сумма сложностей каждого дня из d дней. Сложность дня — это максимальная сложность задания, выполненного в этот день.
Вам дан массив целых чисел jobDifficulty и целое число d. Сложность i-го задания равна jobDifficulty[i].
Верните минимальную сложность расписания заданий. Если вы не можете найти расписание для заданий, верните -1.
Пример:
Input: jobDifficulty = [6,5,4,3,2,1], d = 2
Output: 7
Explanation: 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
C# решение
сопоставлено/оригиналpublic class Solution {
public int MinDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.Length;
if (n < d) {
return -1;
}
int[][] mem = new int[n][];
for (int i = 0; i < n; i++) {
mem[i] = new int[d + 1];
for (int j = 0; j <= d; j++) {
mem[i][j] = -1;
}
}
return MinDiff(0, d, jobDifficulty, mem);
}
private int MinDiff(int i, int daysRemaining, int[] jobDifficulty, int[][] mem) {
if (mem[i][daysRemaining] != -1) {
return mem[i][daysRemaining];
}
if (daysRemaining == 1) {
int res = 0;
for (int j = i; j < jobDifficulty.Length; j++) {
res = Math.Max(res, jobDifficulty[j]);
}
return res;
}
int result = int.MaxValue;
int dailyMaxJobDiff = 0;
for (int j = i; j < jobDifficulty.Length - daysRemaining + 1; j++) {
dailyMaxJobDiff = Math.Max(dailyMaxJobDiff, jobDifficulty[j]);
result = Math.Min(result, dailyMaxJobDiff + MinDiff(j + 1, daysRemaining - 1, jobDifficulty, mem));
}
mem[i][daysRemaining] = result;
return result;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public int MinDifficulty(vector<int>& jobDifficulty, int d) {
int n = jobDifficulty.size();
if (n < d) {
return -1;
}
int[][] mem = new int[n][];
for (int i = 0; i < n; i++) {
mem[i] = new int[d + 1];
for (int j = 0; j <= d; j++) {
mem[i][j] = -1;
}
}
return MinDiff(0, d, jobDifficulty, mem);
}
private int MinDiff(int i, int daysRemaining, vector<int>& jobDifficulty, int[][] mem) {
if (mem[i][daysRemaining] != -1) {
return mem[i][daysRemaining];
}
if (daysRemaining == 1) {
int res = 0;
for (int j = i; j < jobDifficulty.size(); j++) {
res = max(res, jobDifficulty[j]);
}
return res;
}
int result = int.MaxValue;
int dailyMaxJobDiff = 0;
for (int j = i; j < jobDifficulty.size() - daysRemaining + 1; j++) {
dailyMaxJobDiff = max(dailyMaxJobDiff, jobDifficulty[j]);
result = min(result, dailyMaxJobDiff + MinDiff(j + 1, daysRemaining - 1, jobDifficulty, mem));
}
mem[i][daysRemaining] = result;
return result;
}
}Java решение
auto-draft, проверить перед отправкойimport java.util.*;
import java.math.*;
// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
public int MinDifficulty(int[] jobDifficulty, int d) {
int n = jobDifficulty.length;
if (n < d) {
return -1;
}
int[][] mem = new int[n][];
for (int i = 0; i < n; i++) {
mem[i] = new int[d + 1];
for (int j = 0; j <= d; j++) {
mem[i][j] = -1;
}
}
return MinDiff(0, d, jobDifficulty, mem);
}
private int MinDiff(int i, int daysRemaining, int[] jobDifficulty, int[][] mem) {
if (mem[i][daysRemaining] != -1) {
return mem[i][daysRemaining];
}
if (daysRemaining == 1) {
int res = 0;
for (int j = i; j < jobDifficulty.length; j++) {
res = Math.max(res, jobDifficulty[j]);
}
return res;
}
int result = int.MaxValue;
int dailyMaxJobDiff = 0;
for (int j = i; j < jobDifficulty.length - daysRemaining + 1; j++) {
dailyMaxJobDiff = Math.max(dailyMaxJobDiff, jobDifficulty[j]);
result = Math.min(result, dailyMaxJobDiff + MinDiff(j + 1, daysRemaining - 1, jobDifficulty, mem));
}
mem[i][daysRemaining] = result;
return result;
}
}JavaScript решение
сопоставлено/оригиналvar minDifficulty = function(jobDifficulty, d) {
const n = jobDifficulty.length;
if (n < d) return -1;
const mem = Array.from({ length: n }, () => Array(d + 1).fill(-1));
const minDiff = (i, daysRemaining) => {
if (mem[i][daysRemaining] !== -1) return mem[i][daysRemaining];
if (daysRemaining === 1) {
return Math.max(...jobDifficulty.slice(i));
}
let res = Infinity;
let dailyMaxJobDiff = 0;
for (let j = i; j < n - daysRemaining + 1; j++) {
dailyMaxJobDiff = Math.max(dailyMaxJobDiff, jobDifficulty[j]);
res = Math.min(res, dailyMaxJobDiff + minDiff(j + 1, daysRemaining - 1));
}
mem[i][daysRemaining] = res;
return res;
};
return minDiff(0, d);
};Go решение
сопоставлено/оригиналfunc minDifficulty(jobDifficulty []int, d int) int {
n := len(jobDifficulty)
if n < d {
return -1
}
mem := make([][]int, n)
for i := range mem {
mem[i] = make([]int, d+1)
for j := range mem[i] {
mem[i][j] = -1
}
}
return minDiff(0, d, jobDifficulty, mem)
}
func minDiff(i, daysRemaining int, jobDifficulty []int, mem [][]int) int {
if mem[i][daysRemaining] != -1 {
return mem[i][daysRemaining]
}
if daysRemaining == 1 {
res := 0
for j := i; j < len(jobDifficulty); j++ {
if jobDifficulty[j] > res {
res = jobDifficulty[j]
}
}
return res
}
res := int(^uint(0) >> 1)
dailyMaxJobDiff := 0
for j := i; j < len(jobDifficulty)-daysRemaining+1; j++ {
if jobDifficulty[j] > dailyMaxJobDiff {
dailyMaxJobDiff = jobDifficulty[j]
}
next := minDiff(j+1, daysRemaining-1, jobDifficulty, mem)
if res > dailyMaxJobDiff+next {
res = dailyMaxJobDiff + next
}
}
mem[i][daysRemaining] = res
return res
}Algorithm
Определение состояния:
Индекс i (индекс первой задачи на сегодняшний день в массиве jobDifficulty) и день d (количество оставшихся дней) будут определять состояние динамического программирования. min_diff(i, d) обозначает минимальную сложность при начале с i-й задачи с оставшимися d днями. min_diff(0, d) будет окончательным ответом, так как он представляет начало с начала массива задач и завершение всех задач за ровно d дней.
Функция перехода состояния:
Задача с индексом j будет первой задачей на следующий день, следовательно, задачи, которые должны быть завершены сегодня, это все задачи с индексами между i и j, то есть jobDifficulty[i
]. Поскольку сложность дня — это максимальная сложность выполненной в этот день задачи, к сумме сложностей задач будет добавляться максимум из jobDifficulty[i
]. Формулируем функцию перехода состояния следующим образом: min_diff(i, d) = min_diff(j, d - 1) + max(jobDifficulty[i
]) для всех j > i.
Базовый случай:
Когда остается только 1 день, необходимо завершить все незавершенные задачи в этот день и увеличить сложность расписания задач на максимальную сложность этих задач.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.