Grokking the Coding Interview: Patterns for Coding Questions
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Problem Challenge 2: Maximum CPU Load
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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
Explanation: None of the jobs overlap, therefore we will take the maximum load of any job which is 15.

Example 3:

Jobs: [[1,4,2], [2,4,1], [3,6,5]]
Output: 8
Explanation: Maximum CPU load will be 8 as all jobs overlap during the time interval [3,4].

Solution

To solve this problem, we'll use a priority queue to keep track of overlapping tasks and their CPU loads. The priority queue helps us efficiently manage which tasks are currently running and their cumulative load. We'll first sort the tasks by their start times. As we iterate through the tasks, we'll remove any tasks from the queue that have already ended before the current task's start time, ensuring we only consider the relevant tasks. This approach allows us to dynamically calculate the current CPU load and update the maximum load observed.

This method works well because it leverages sorting and a priority queue to maintain an efficient and dynamic set of tasks. By sorting the tasks initially, we ensure we process them in the correct order. Using a priority queue allows us to efficiently manage and update the set of overlapping tasks and their loads. This ensures that our algorithm is both efficient and scalable, handling overlapping tasks without excessive complexity.

Step-by-Step Algorithm

  1. Sort the Jobs:

    • Arrange the jobs based on their start times in ascending order.
    • This ensures we process each job in the order they start, making it easier to track overlapping jobs.

  2. Initialize Variables:

    • maxCPULoad: to keep track of the maximum CPU load observed at any time.
    • currentCPULoad: to keep track of the current total CPU load.
    • minHeap: a priority queue to keep track of ongoing jobs, sorted by their end times.

  3. Process Each Job:

    • For each job in the sorted list:
      • Remove all jobs from the minHeap that have ended before the current job's start time. Decrease currentCPULoad by the CPU load of each removed job.
      • Add the current job to the minHeap and increase currentCPULoad by the CPU load of the current job.
      • Update maxCPULoad if currentCPULoad is greater than the current maxCPULoad.

  4. Return the Maximum CPU Load:

    • After processing all jobs, the maxCPULoad will hold the maximum CPU load at any point in time.

Algorithm Walkthrough

  • Input: [[1, 4, 3], [2, 5, 4], [7, 9, 6]]

  1. Sort the Jobs:

    • Sorted jobs: [[1, 4, 3], [2, 5, 4], [7, 9, 6]]

  2. Initialize Variables:

    • maxCPULoad: 0
    • currentCPULoad: 0
    • minHeap: empty

  3. Process Each Job:

    • Job 1: [1, 4, 3]
      • Add to minHeap: [1, 4, 3]
      • currentCPULoad: 3
      • maxCPULoad: 3
    • Job 2: [2, 5, 4]
      • No jobs end before the current job starts.
      • Add to minHeap: [1, 4, 3], [2, 5, 4]
      • currentCPULoad: 7
      • maxCPULoad: 7
    • Job 3: [7, 9, 6]
      • Remove jobs [1, 4, 3] and [2, 5, 4] from minHeap.
      • currentCPULoad: 0
      • Add to minHeap: [7, 9, 6]
      • currentCPULoad: 6
      • maxCPULoad: remains 7

  4. Return Result:

    • Maximum CPU load: 7
Image

Code

Here is what our algorithm will look like:

Python3
Python3
. . . .

Time Complexity

The time complexity of the above algorithm is O(N*logN), where ‘N’ is the total number of jobs. This is due to the sorting that we did in the beginning. Also, while iterating the jobs, we might need to poll/offer jobs to the priority queue. Each of these operations can take O(logN). Overall our algorithm will take O(NlogN).

Space Complexity

The space complexity of the above algorithm will be O(N), which is required for sorting. Also, in the worst case, we have to insert all the jobs into the priority queue (when all jobs overlap) which will also take O(N) space. The overall space complexity of our algorithm is O(N).

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible