Problem

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.

Examples

Example 1:

1
2
3
4

Input: 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:

1
2
3

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:

1
2
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

Method 1 - Sorting

This problem follows the Merge Intervals Problem pattern..

It is almost same as Maximum Intervals Overlap Count, where we for e.g. we aim to find the peak number of concurrent meetings.

Similarly, for Maximum CPU Load, we need to determine the peak number of concurrent jobs and maintain a running total of the CPU load over time to identify the maximum load encountered.

Here is the approach:

  1. Sort Events: Convert job intervals into start and end events, and sort these events by start time.
  2. Track CPU Load: As we iterate through these jobs, we track overlaps incrementally as done previously. We use a min heap to keep track of current jobs and their loads. Add the load when a job starts and subtract the load when a job ends.
  3. Calculate Maximum Load: Maintain a running total of the current CPU load and update the maximum load encountered during the process.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    public int findMaxCPULoad(int[][] jobs) {
        Arrays.sort(jobs, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        int maxLoad = 0, currentLoad = 0;

        for (int[] job : jobs) {
            while (!minHeap.isEmpty() && minHeap.peek()[1] <= job[0]) {
                currentLoad -= minHeap.poll()[2];
            }
            minHeap.offer(job);
            currentLoad += job[2];
            maxLoad = Math.max(maxLoad, currentLoad);
        }

        return maxLoad;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[][] jobs1 = {{1, 4, 3}, {2, 5, 4}, {7, 9, 6}};
        int[][] jobs2 = {{1, 3, 5}, {4, 6, 5}, {7, 9, 10}};
        System.out.println(sol.findMaxCPULoad(jobs1)); // Output: 7
        System.out.println(sol.findMaxCPULoad(jobs2)); // Output: 10
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def findMaxCPULoad(self, jobs: List[List[int]]) -> int:
        jobs.sort(key=lambda x: x[0])
        max_load = 0
        current_load = 0
        min_heap = []

        for job in jobs:
            while min_heap and min_heap[0][1] <= job[0]:
                current_load -= heapq.heappop(min_heap)[2]
            heapq.heappush(min_heap, (job[0], job[1], job[2]))
            current_load += job[2]
            max_load = max(max_load, current_load)

        return max_load

if __name__ == "__main__":
    sol = Solution()
    jobs1 = [[1, 4, 3], [2, 5, 4], [7, 9, 6]]
    jobs2 = [[1, 3, 5], [4, 6, 5], [7, 9, 10]]
    print(sol.findMaxCPULoad(jobs1)) # Output: 7
    print(sol.findMaxCPULoad(jobs2)) # Output: 10

Complexity

  • ⏰ Time complexity: O(n log n) for sorting job intervals and managing heap operations, where n is the number of jobs.
  • 🧺 Space complexity: O(n) for storing events and heap data.