Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Problem Challenge 2: Maximum CPU Load (hard)

Problem Statement

We are given a list of Jobs. Each job has a Start time, an End time, and a CPU load when it is running. Our goal is to find the maximum CPU load at any time if all the jobs are running on the same machine.

Example 1:

Jobs: [[1,4,3], [2,5,4], [7,9,6]]
Output: 7
Explanation: Since [1,4,3] and [2,5,4] overlap, their maximum CPU load (3+4=7) will be when both the jobs are running at the same time i.e., during the time interval (2,4).

Example 2:

Jobs: [[6,7,10], [2,4,11], [8,12,15]]
Output: 15

.....

.....

.....

Like the course? Get enrolled and start learning!
Enrique Fernández

Enrique Fernández

· 2 years ago

Not only for this exercise but for many others... In my case my code works for all the testcases, excepting the edge cases commented by others.

With these few testcases it's hard for us to evaluate if our alternatives are okay or not.

Show 1 reply
Mohammed Dh Abbas

Mohammed Dh Abbas

· 2 years ago

from heapq import *


#class job:
#  def __init__(self, start, end, cpu_load):
#    self.start = start
#    self.end = end
#    self.cpuLoad = cpu_load

# You can override/modify __lt__ as per your need
#setattr(Job, "__lt__", lambda self, other: write logic here)

class Solution:
  def findMaxCPULoad(self, jobs):
    max_cpu_load = 0

    sum = 0 
    
    jobs.sort(key=lambda x: x.start)

    def overlap(a, b):
      return b.start < a.end

    for i in range(len(jobs)):
      
      if i == 0 or not overlap(jobs[i-1], jobs[i]):
        sum = jobs[i].cpuLoad
      else:
        sum += jobs[i].cpuLoad

      max_cpu_load = max(max_cpu_load, sum)
      
    return max_cpu_load
Show 2 replies
A

ahonliu

· 2 years ago

[[1, 9, 3], [2, 5, 4], [7, 9, 6]]

Expected: 9

My code submission passes, but it should fail on this case (my return is 13).

H

hubert

· 3 years ago

Hello,

I wrote a solution that passed the tests even though it was wrong (for some cases). One case where my solution fails is: [[1, 4, 3], [2, 5, 4], [7, 9, 6]]

Maybe you can add that as an additional test case?

M

Michael Baggie

· 4 years ago

Does anyone know what number this would be on leetcode?

A

Amitrajit Manna

· 4 years ago

Can't a simpler implementation of adding up the loads of an interval work.

need to sort the array

def max_cpu_load(jobs):

if len(jobs) < 2: return jobs[0][2]

start = jobs[0][0] end = jobs[0][1] load = jobs[0][2] max_load = load

for i in range(1, len(jobs)): j = jobs[i] if j[0] < end: load += j[2] max_load = max( load, max_load ) end = max( end, j[1]) else: load = j[2] max_load = max(load, max_load) return max_load

print( max_cpu_load([[1,4,3], [2,5,4], [7,9,6]]) ) print( max_cpu_load([[2,4,11], [6,7,10], [8,12,15]]) ) print( max_cpu_load([[1,4,2], [2,4,1], [3,6,5]]) )

Reading Progress

0%