Fluent::Programmer

    Home Blog About
  • Home
  • Blog
  • About
  • c++
  • beautiful-code-series
  • linux
  • algorithms
  • assembly-language
  • c-programming
  • network-programming

Dynamic programming - Part 2 👋

  • Fluent Programmer
  • March 11, 2023
  •   3 min read

Quick summary ↬  In this article we apply dynamic programming to one of the hard leetcode problem: 1335. Minimum Difficulty of a Job Schedule and explore ideas and different solutions.

Problem statement

You want to schedule a list of jobs in d days. Jobs are dependent and sequential in nature. Example: to complete the job i+1, you need to complete the job i and anything before that.

The core condition is every day you need to complete atleast one job. The difficulty of Job Schedule is sum of difficulty of each day of the d days. The difficulty of a day is maximum difficulty of the job done on that day.

Input: An integer array which represents the Job Difficulty and an integer d. The difficulty of ith job is represented by JobDifficulty[i].

Return maximum difficulty of job schedule. If you cannot find just return -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
beautiful-code-5

For the above example the best solution is to do the jobs with difficulty 6,5,4,3,2 in day 1 and then in day 2 just do the job number 1.

Solution

State variables and a function to solve

Let’s first find the state variables. As we solve the subproblems of the actual problem what are all the arguments that changes needs to known. If we read the problem carefully, we need to add couple of questions to solve these overlapping subproblems.

  1. How many jobs to add in a certain day? How it affects the future subproblem decisions? How it connects with the previous subproblem decision?

Okay, based on the first question - we could define that “day” is one of the state variables. Other state variable is “starting job number” or let’s call it index of JobDifficulty array.

Now the function that we need to solve for every subproblem is f(JobIndex, day).

For example, Initially the values passed to the function is f(1, 1). Maximum number of jobs that can be added to any particular day is equal to Total number of jobs remaining - (Total number of days remaining-current_day); Let’s call this MMM_MAX. Same formula applies to day 2, day 3, day 4……..day n, etc.

At the minimum every day at least one job needs to be allocated. Now to solve every subproblem, the function should find a value between JobIndex to MMM_MAX with the goal that at the end we find the minimal difficulty of a job schedule. (i.e) All the max elements in the array should be grouped together as much as possible in a single day.

About The Author

Fluentprogrammer doesn't need coffee to program. They run on pure caffeine and lines of code.

Email Newsletter

Table of Contents

  • Problem statement
  • Solution
    • State variables and a function to solve
  • C++
  • Systems & Network
  • C programming
  • Beautiful code
  • Design patterns
  • Linux
  • Open Source
  • Algorithms
  • Data Structures
  • System design
  • Distributed systems
  • Kernel
  • Assembly language
  • Hardware
  • Ultra Low Latency
  • Inspiration

Unhealthy love with dark corners of C++

Founded by an engineer to help engineers. 2021–2023.

Fluentprogrammer.com is a brand name managed by Abyan, Inc.

  • About us
  • Privacy policy