Job scheduling program in python

Tech Evangelist, Instructor, Polyglot Developer with a passion for innovative technology, Father & Health Activist

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

Timothy Mugayi

Tech Evangelist, Instructor, Polyglot Developer with a passion for innovative technology, Father & Health Activist

Suppose we have a list of intervals where each interval contains three values [start, end, profit]. We can perform only one task at a time, we have to find the most amount of profit we can get.

So, if the input is like intervals = [[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]], then the output will be 350, as we can take these two intervals [1, 2, 100] and [2, 100, 250]

To solve this, we will follow these steps

• d := an empty map that contains lists as values
• n := 0
• for each [start, end, profit] in intervals, do
  • if end > n, then
    • n := end
• insert pair [start, end] into d[end]
• A := a list of size n + 1 and fill with 0
• for end in range 0 to size of A, do
  • if end is in d, then
    • for each [start, profit] pair in d[end], do
      • A[end] := maximum of A[end], [A[start] + profit] and A[end - 1]
  • otherwise,
    • A[end] := A[end - 1]
• return last value of A

Example [Python]

Let us see the following implementation to get better understanding −

 Live Demo

from collections import defaultdict
class Solution:
   def solve[self, intervals]:
      d = defaultdict[list]
      n = 0
      for start, end, profit in intervals:
         if end > n:
            n = end
         d[end].append[[start, profit]]
      A = [0 for i in range[n + 1]]
      for end in range[len[A]]:
         if end in d:
            for start, profit in d[end]:
               A[end] = max[A[end], A[start] + profit, A[end - 1]]
         else:
            A[end] = A[end - 1]
      return A[-1]
ob = Solution[]
intervals = [[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]
print[ob.solve[intervals]]

Input

[[1, 2, 100],[3, 5, 40],[6, 19, 150],[2, 100, 250]]

Output

350

Updated on 12-Dec-2020 09:53:00

• Related Questions & Answers
• Maximum Profit in Job Scheduling in C++
• C++ code to get maximum profit by house making
• Program to find maximum profit we can make by holding and selling profit in Python
• Program to find the maximum profit we can get by buying on stock market once in Python
• Program to find maximum profit by selling diminishing-valued colored balls in Python
• Program to find the maximum profit we can get by buying on stock market multiple times in Python
• Program to find maximum profit we can get by buying and selling stocks with a fee in Python?
• Program to find maximum profit we can make by buying and selling stocks in Python?
• Find Jobs involved in Weighted Job Scheduling in C++
• Program to find maximum profit by cutting the rod of different length in C++
• C++ program to find maximum profit we can make by making hamburger and chicken burgers
• Program to find maximum credit we can get by finishing some assignments in python
• Program to find maximum profit we can make after k Buy and Sell in python
• Program to find maximum profit after cutting rods and selling same length rods in Python
• Maximum profit by buying and selling a share at most twice

How do you schedule jobs in Python?

What is a job scheduling algorithm?

How do you solve job scheduling problems?