Home/

...

/

Problem Challenge 2

Problem Challenge 2

Dry-run templates

This is the implementation of the solution provided for the problem posed in the Problem Challenge 2 lesson:

Press + to interact
Python 3.5
from heapq import *
class job:
  def __init__(self, start, end, cpu_load):
    self.start = start
    self.end = end
    self.cpu_load = cpu_load
  def __lt__(self, other):
    # min heap based on job.end
    return self.end < other.end
def find_max_cpu_load(jobs):
  # sort the jobs by start time
  jobs.sort(key=lambda x: x.start)
  max_cpu_load, current_cpu_load = 0, 0
  min_heap = []
  for j in jobs:
    # remove all the jobs that have ended
    while(len(min_heap) > 0 and j.start >= min_heap[0].end):
      current_cpu_load -= min_heap[0].cpu_load
      heappop(min_heap)
    # add the current job into min_heap
    heappush(min_heap, j)
    current_cpu_load += j.cpu_load
    max_cpu_load = max(max_cpu_load, current_cpu_load)
  return max_cpu_load
def main():
  print("Maximum CPU load at any time: " + str(find_max_cpu_load([job(1, 4, 3), job(2, 5, 4), job(7, 9, 6)])))
  print("Maximum CPU load at any time: " + str(find_max_cpu_load([job(6, 7, 10), job(2, 4, 11), job(8, 12, 15)])))
  print("Maximum CPU load at any time: " + str(find_max_cpu_load([job(1, 4, 2), job(2, 4, 1), job(3, 6, 5)])))
main()

Students may be encouraged to run through the provided solution with the following sample inputs:

Sample Input #1

jobs: [job(1, 4, 3), job(2, 5, 4), job(7, 9, 6)]

Iteration No.

Line No.

min_heap

current_cpu_load

max_cpu_load

-

18-19

[]

0

0

1

27-29

[(1,4,3)]

3

3

2

27-29

[(1,4,3),(2,5,4)]

7

7

3

23-25

[]

0

0

3

27-29

[(7,9,6)]

6

7

Sample Input #2

jobs: [job(6, 7, 10), job(2, 4, 11), job(8, 12, 15)]

Iteration No.

Line No.

min_heap

current_cpu_load

max_cpu_load

-

18-19

[]

0

0

1

27-29

[(2,4,11)]

11

11

2

23-25

[]

0

11

2

27-29

[(6,7,10)]

10

11

3

23-25

[]

0

11

3

27-29

[(8,12,15)]

15

15

Step-by-step solution construction

Let’s first write code to find the sum of workloads of all the jobs without considering the intervals (lines 34-43). Also, we will be pushing each job into a heap to be used in the next steps.

Notice the function print_arr used to print the trace log for a better understanding of the program execution. print_arr is a global function that prints an array of objects of type job. For each object, __str__ is called by default to convert the object to string. We use this fact and override __str__ for class job to return its string representation (lines 14-15).

Press + to interact
Python 3.5
from heapq import *
class job:
  def __init__(self, start, end, cpu_load):
    self.start = start
    self.end = end
    self.cpu_load = cpu_load
  def __lt__(self, other):
    # min heap based on job.end
    return self.end < other.end
  
  def __str__(self):
    return "("+ str(self.start)+", "+ str(self.end)+ ", " + str(self.cpu_load) + ")"
 
def print_arr(min_heap):
    print("[", end="")
    index = 0
    for j in min_heap:
      if(index > 0):
        print(",",end="")
      print(j,end="")
      index += 1
    print("]")
def find_max_cpu_load(jobs):
  # sort the jobs by start time
  jobs.sort(key=lambda x: x.start)
  max_cpu_load, current_cpu_load = 0, 0
  min_heap = []
  index = 0
  for j in jobs:
    print("\tIteration: "+str(index))
    index +=1
    # add the current job into min_heap
    heappush(min_heap, j)
    print("\t\tmin_heap after adding current job to the min_heap: ",end = "")
    print_arr(min_heap)
    current_cpu_load += j.cpu_load
    print("\t\tcurrent_cpu_load: " + str(current_cpu_load))
    max_cpu_load = max(max_cpu_load, current_cpu_load)
    print("\t\tmax_cpu_load: " + str(max_cpu_load))    
  return max_cpu_load
def main():
  jobs = [[job(1, 4, 3), job(2, 5, 4), job(7, 9, 6)],
          [job(6, 7, 10), job(2, 4, 11), job(8, 12, 15)],
          [job(1, 4, 2), job(2, 4, 1), job(3, 6, 5)]]
  for j in jobs:
    print("Finding maximum load for: ", end="")
    print_arr(j)
    result = find_max_cpu_load(j)
    print("Maximum CPU load at any time: " + str(result))
    print(("-"*100)+"\n") 
main()

Let’s refine the code to take the intervals into consideration.

Before a new job to the min_heap, we remove all the jobs that have ended before the current job. Since we compute current_cpu_load for the jobs present in the min_heap, when we pop the jobs from the min_heap, we also exclude current_work_load for the jobs that have ended (lines 41-43).

We will keep adding the overlapped jobs to the min_heap until a non-overlapping job is found (line 47). We will also compute the sum of the workloads of these jobs (line 50).

We also maintain another variable max_cpu_load to track the maximum CPU load of the overlapping jobs at any time. When the iteration of all the jobs is complete, the value in max_cpu_load represents the maximum load attained during the job executions.

Press + to interact
Python 3.5
from heapq import *
class job:
  def __init__(self, start, end, cpu_load):
    self.start = start
    self.end = end
    self.cpu_load = cpu_load
  def __lt__(self, other):
    # min heap based on job.end
    return self.end < other.end
  def __str__(self):
    return "("+ str(self.start)+", "+ str(self.end)+ ", " + str(self.cpu_load) + ")"
def print_arr(min_heap):
    print("[", end="")
    index = 0
    for j in min_heap:
      if(index > 0):
        print(",",end="")
      print(j,end="")
      index += 1
    print("]")
def find_max_cpu_load(jobs):
  # sort the jobs by start time
  jobs.sort(key=lambda x: x.start)
  max_cpu_load, current_cpu_load = 0, 0
  min_heap = []
  index = 0
  for j in jobs:
    print("\tIteration: "+str(index))
    print("\t\tmin_heap: ",end="")
    print_arr(min_heap)
    # remove all the jobs that have ended
    print("\t\tremoving all the jobs that have ended before the current job: " + str(j))
    while(len(min_heap) > 0 and j.start >= min_heap[0].end):
      current_cpu_load -= min_heap[0].cpu_load
      heappop(min_heap)
    print("\t\tmin_heap after removing all earlier jobs: ", end= "")
    print_arr(min_heap)
    # add the current job into min_heap
    heappush(min_heap, j)
    print("\t\tmin_heap after adding current job to the min_heap: ",end = "")
    print_arr(min_heap)
    current_cpu_load += j.cpu_load
    print("\t\tcurrent_cpu_load: " + str(current_cpu_load))
    max_cpu_load = max(max_cpu_load, current_cpu_load)
    print("\t\tmax_cpu_load: " + str(max_cpu_load))
    index +=1
    
  return max_cpu_load
def main():
  jobs = [[job(1, 4, 3), job(2, 5, 4), job(7, 9, 6)],
          [job(6, 7, 10), job(2, 4, 11), job(8, 12, 15)],
          [job(1, 4, 2), job(2, 4, 1), job(3, 6, 5)]]
  for j in jobs:
    print("Finding maximum load for: ", end="")
    print_arr(j)
    result = find_max_cpu_load(j)
    print("Maximum CPU load at any time: " + str(result))
    print(("-"*100)+"\n")
main()