groups Archives - Huahua's Tech Road

You want to schedule a list of jobs in d days. Jobs are dependent (i.e To work on the i-th job, you have to finish all the jobs j where 0 <= j < i).

You have to finish at least one task every day. The difficulty of a job schedule is the sum of difficulties of each day of the d days. The difficulty of a day is the maximum difficulty of a job done in that day.

Given an array of integers jobDifficulty and an integer d. The difficulty of the i-th job is jobDifficulty[i].

Return the minimum difficulty of a job schedule. If you cannot find a schedule for the jobs return -1.

Example 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

Example 2:

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

Example 3:

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

Example 4:

Input: jobDifficulty = [7,1,7,1,7,1], d = 3
Output: 15

Example 5:

Input: jobDifficulty = [11,111,22,222,33,333,44,444], d = 6
Output: 843

Constraints:

1 <= jobDifficulty.length <= 300
0 <= jobDifficulty[i] <= 1000
1 <= d <= 10

Solution: DP

dp[i][k] := min difficulties to schedule jobs 1~i in k days.

Schedule 1 ~ j in k – 1 days and schedule j + 1 ~ i in 1 day.

Init: dp[0][0] = 0
Transition: dp[i][k] := min(dp[j][k -1] + max(jobs[j + 1 ~ i]), k – 1 <= j < i
Answer: dp[n][d]

Time complexity: O(n^2*d)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int minDifficulty(vector<int>& jobs, int d) {

const int n = jobs.size();

if (d > n) return -1;

vector<vector<int>> dp(n + 1, vector<int>(d + 1, INT_MAX / 2));

dp[0][0] = 0;

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

for (int j = i - 1, md = 0; j >= 0; --j) {

md = max(md, jobs[j]);

for (int k = 1; k <= min(i, d); ++k)

dp[i][k] = min(dp[i][k], dp[j][k - 1] + md);

}

return dp[n][d];

}

};

Problem

Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.

Note:
If n is the length of array, assume the following constraints are satisfied:

1 ≤ n ≤ 1000

1 ≤ m ≤ min(50, n)

Examples:

Input: nums = [7,2,5,10,8] m = 2 Output: 18 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

Solution: DP

Time complexity: O(n^2*m)

Space complexity: O(n*m)

C++ / Recursion + Memorization

// Author: Huahua

// Running time: 111 ms

class Solution {

public:

int splitArray(vector<int>& nums, int m) {

const int n = nums.size();

sums_ = vector<int>(n);

mem_ = vector<vector<int>>(n, vector<int>(m + 1, INT_MAX));

sums_[0] = nums[0];

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

sums_[i] = sums_[i - 1] + nums[i];

return splitArray(nums, n - 1, m);

}

private:

vector<vector<int>> mem_;

vector<int> sums_;

// min of largest sum of spliting nums[0] ~ nums[k] into m groups

int splitArray(const vector<int>& nums, int k, int m) {

if (m == 1) return sums_[k];

if (m > k + 1) return INT_MAX;

if (mem_[k][m] != INT_MAX) return mem_[k][m];

int ans = INT_MAX;

for (int i = 0; i < k; ++i)

ans = min(ans, max(splitArray(nums, i, m - 1), sums_[k] - sums_[i]));

return mem_[k][m] = ans;

}

};

C++ / DP

// Author: Huahua

// Running time: 90 ms

class Solution {

public:

int splitArray(vector<int>& nums, int m) {

const int n = nums.size();

vector<int> sums(n);

// dp[i][j] := min of largest sum of splitting nums[0] ~ nums[j] into i groups.

vector<vector<int>> dp(m + 1, vector<int>(n, INT_MAX));

sums[0] = nums[0];

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

sums[i] = sums[i - 1] + nums[i];

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

dp[1][i] = sums[i];

for (int i = 2; i <= m; ++i)

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

for (int k = 0; k < j; ++k)

dp[i][j] = min(dp[i][j], max(dp[i - 1][k], sums[j] - sums[k]));

return dp[m][n - 1];

}

};

Solution: Binary Search

Time complexity: O(log(sum(nums))*n)

Space complexity: O(1)

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

int splitArray(vector<int>& nums, int m) {

long l = *max_element(begin(nums), end(nums));

long r = accumulate(begin(nums), end(nums), 0L) + 1;

while (l < r) {

long limit = (r - l) / 2 + l;

if (min_groups(nums, limit) > m)

l = limit + 1;

else

r = limit;

}

return l;

}

private:

int min_groups(const vector<int>& nums, long limit) {

long sum = 0;

int groups = 1;

for (int num : nums) {

if (sum + num > limit) {

sum = num;

++groups;

} else {

sum += num;

}

return groups;

}

};

Posts tagged as “groups”

花花酱 LeetCode 1335. Minimum Difficulty of a Job Schedule

Solution: DP

C++

花花酱 LeetCode 410. Split Array Largest Sum

Problem

Solution: DP

Solution: Binary Search