Maximum CPU Load (Peak Overlap)

▶

Steps

setup

Initialize events list

We start by creating an empty list to hold all start and end events derived from the jobs.

💡 This step sets up the data structure that will allow us to process all load changes in chronological order.

Line:

events = []

💡 An empty events list is the foundation for capturing all load changes.

insert

Add start event for job 1

Add the start event (time=1, load=3) for the first job to the events list.

💡 Each job contributes two events: a start with positive load and an end with negative load.

Line:

events.append((start, load))  # (1, 3)

💡 Start events increase the current load when processed.

insert

Add end event for job 1

Add the end event (time=4, load=-3) for the first job to the events list.

💡 End events decrease the current load when processed, marking job completion.

Line:

events.append((end, -load))  # (4, -3)

💡 End events signal when a job's load should be subtracted.

insert

Add start event for job 2

Add the start event (time=2, load=4) for the second job to the events list.

💡 We continue adding all job events to process them in chronological order later.

Line:

events.append((start, load))  # (2, 4)

💡 This event will increase the load when processed.

insert

Add end event for job 2

Add the end event (time=5, load=-4) for the second job to the events list.

💡 End events mark when the load from a job should be removed.

Line:

events.append((end, -load))  # (5, -4)

💡 This event will decrease the load when processed.

insert

Add start event for job 3

Add the start event (time=7, load=6) for the third job to the events list.

💡 We add all job events before sorting to process them in order.

Line:

events.append((start, load))  # (7, 6)

💡 This event will increase the load when processed.

insert

Add end event for job 3

Add the end event (time=9, load=-6) for the third job to the events list.

💡 Completing the events list with all job end events.

Line:

events.append((end, -load))  # (9, -6)

💡 This event will decrease the load when processed.

expand

Sort events by time

Sort the events list by the event time to process load changes chronologically.

💡 Sorting ensures we apply load changes in the correct order to track overlaps accurately.

Line:

events.sort(key=lambda x: x[0])

💡 Sorted events allow a linear sweep to compute current load at each time point.

traverse

Process event at time 1: start job 1

Process the event at time 1 which adds load 3 to current_load.

💡 Applying load changes in order updates the current CPU load accurately.

Line:

current_load += load_change  # current_load = 0 + 3

💡 Starting job 1 increases current load to 3.

compare

Update max_load after time 1 event

Compare current_load (3) with max_load (0) and update max_load to 3.

💡 Tracking max_load ensures we remember the peak CPU load seen so far.

Line:

max_load = max(max_load, current_load)  # max_load = 3

💡 max_load reflects the highest load encountered after processing each event.

traverse

Process event at time 2: start job 2

Process the event at time 2 which adds load 4 to current_load (3 + 4 = 7).

💡 Overlapping jobs increase the CPU load cumulatively.

Line:

current_load += load_change  # current_load = 3 + 4

💡 Starting job 2 overlaps with job 1, increasing load to 7.

compare

Update max_load after time 2 event

Compare current_load (7) with max_load (3) and update max_load to 7.

💡 We update max_load to reflect the new peak load.

Line:

max_load = max(max_load, current_load)  # max_load = 7

💡 max_load now correctly tracks the peak CPU load during overlapping jobs.

traverse

Process event at time 4: end job 1

Process the event at time 4 which subtracts load 3 from current_load (7 - 3 = 4).

💡 Job 1 ends, so its load is removed from the current load.

Line:

current_load += load_change  # current_load = 7 - 3

💡 Removing job 1's load decreases current load to 4.

compare

Update max_load after time 4 event

Compare current_load (4) with max_load (7); max_load remains 7.

💡 max_load only updates if current_load exceeds it.

Line:

max_load = max(max_load, current_load)  # max_load = 7

💡 Peak load remains 7 despite load decrease.

traverse

Process event at time 5: end job 2

Process the event at time 5 which subtracts load 4 from current_load (4 - 4 = 0).

💡 Job 2 ends, so its load is removed, leaving no active jobs.

Line:

current_load += load_change  # current_load = 4 - 4

💡 No jobs running after time 5, current load is zero.

compare

Update max_load after time 5 event

Compare current_load (0) with max_load (7); max_load remains 7.

💡 max_load only updates if current_load exceeds it.

Line:

max_load = max(max_load, current_load)  # max_load = 7

💡 Peak load remains 7 after jobs end.

traverse

Process event at time 7: start job 3

Process the event at time 7 which adds load 6 to current_load (0 + 6 = 6).

💡 Job 3 starts after previous jobs ended, increasing load to 6.

Line:

current_load += load_change  # current_load = 0 + 6

💡 Load increases to 6, but this is less than max_load 7.

compare

Update max_load after time 7 event

Compare current_load (6) with max_load (7); max_load remains 7.

💡 max_load only updates if current_load exceeds it.

Line:

max_load = max(max_load, current_load)  # max_load = 7

💡 Peak load remains 7 despite new job starting.

traverse

Process event at time 9: end job 3

Process the event at time 9 which subtracts load 6 from current_load (6 - 6 = 0).

💡 Job 3 ends, so its load is removed, leaving no active jobs.

Line:

current_load += load_change  # current_load = 6 - 6

💡 No jobs running after time 9, current load is zero.

reconstruct

Return max_load as final answer

After processing all events, return max_load which is 7, the peak CPU load.

💡 The maximum CPU load is the highest load recorded during the event processing.

Line:

return max_load  # returns 7

💡 The algorithm correctly identifies the peak load during overlapping jobs.

def find_max_cpu_load(jobs):
    events = []  # STEP 1
    for start, end, load in jobs:
        events.append((start, load))  # STEP 2,4,6
        events.append((end, -load))   # STEP 3,5,7
    events.sort(key=lambda x: x[0])  # STEP 8

    current_load = 0  # STEP 1
    max_load = 0      # STEP 1
    for _, load_change in events:
        current_load += load_change  # STEP 9,11,13,15,17,19
        max_load = max(max_load, current_load)  # STEP 10,12,14,16,18
    return max_load  # STEP 20

if __name__ == '__main__':
    jobs = [[1,4,3], [2,5,4], [7,9,6]]
    print(find_max_cpu_load(jobs))  # Output: 7

📊

Maximum CPU Load (Peak Overlap) - Watch the Algorithm Execute, Step by Step

Watching each event processed helps you understand how overlapping intervals contribute to CPU load and why sorting events by time is crucial.

insertmin-heap

empty heap

insertmin-heap

(1, +3)

0

insertmin-heap

(1, +3)

0

(4, -3)

1

insertmin-heap

(1, +3)

0

(4, -3)

1

(2, +4)

2

insertmin-heap

(1, +3)

0

(4, -3)

1

(2, +4)

2

(5, -4)

3

insertmin-heap

(1, +3)

0

(4, -3)

1

(2, +4)

2

(5, -4)

3

(7, +6)

4

insertmin-heap

(1, +3)

0

(4, -3)

1

(2, +4)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

expandmin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

traversemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 3

comparemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 3

traversemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 7

comparemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 7

traversemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 4

comparemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 7

traversemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 0

comparemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 7

traversemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 6

comparemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 7

traversemin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 0

peekmin-heap

(1, +3)

0

(2, +4)

1

(4, -3)

2

(5, -4)

3

(7, +6)

4

(9, -6)

5

Added: 7

Key Takeaways

✓ Transforming job intervals into start and end events allows a linear sweep to efficiently compute overlapping loads.

This insight is hard to see from code alone because the event transformation and sorting are subtle but critical steps.

✓ Sorting events by time ensures load changes are applied in chronological order, accurately reflecting overlaps.

Without sorting, the algorithm would miscalculate overlaps, which is easier to understand visually.

✓ Tracking current_load and updating max_load after each event reveals the peak CPU load during job overlaps.

Seeing load increase and decrease step-by-step clarifies why max_load updates only when current_load exceeds it.

Practice

1. The following code attempts to find the k-th smallest pair distance using a heap-based approach. Identify the line containing the subtle bug that can cause incorrect results.

medium

A. Line 8: Loop runs k-1 times instead of k times.

B. Line 5: Incorrect heap initialization with pairs from adjacent elements.

C. Line 2: Missing sorting of the input array before processing pairs.

D. Line 10: Incorrect condition for pushing next pair into the heap.

Solution

1. Step 1: Check for sorting

   The input array is not sorted before pushing pairs, so pair distances are incorrect or unordered.

2. Step 2: Verify heap initialization and loop

   Heap initialization and loop logic are correct assuming sorted input; condition and loop count are proper.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sorting is essential for correct pair distance ordering [OK]

Hint: Always sort before generating pairs for distance calculations [OK]

Common Mistakes:

• Forgetting to sort input array
• Off-by-one in loop count
• Wrong heap push condition

2. What is the average and worst-case time complexity of the Quickselect algorithm for finding the kth largest element in an unsorted array of size n?

medium

A. Average O(n log n), Worst O(n^2)

B. Average O(n), Worst O(n^2)

C. Average O(n^2), Worst O(n^2)

D. Average O(n), Worst O(n log n)

Solution

1. Step 1: Analyze average case

   Quickselect partitions array and recurses on one side, averaging O(n) time.

2. Step 2: Analyze worst case

   Poor pivot choices cause unbalanced partitions, degrading to O(n^2) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Average linear, worst quadratic time complexity [OK]

Hint: Average linear time, worst quadratic due to bad pivots [OK]

Common Mistakes:

• Assuming always O(n log n)
• Confusing average and worst cases
• Ignoring worst-case pivot effects

3. What is the time complexity of the optimal bucket sort approach for finding the top k frequent elements in an array of size n, and why?

medium

A. O(n²) because nested loops iterate over frequencies and elements.

B. O(n log n) because sorting is involved in frequency ordering.

C. O(k log n) because a heap of size k is maintained during iteration.

D. O(n) because frequency counting and bucket placement are linear, and iterating buckets is at most n.

Solution

1. Step 1: Analyze frequency counting

   Counting frequencies requires one pass over n elements -> O(n).

2. Step 2: Analyze bucket creation and iteration

   Creating buckets and placing elements is O(n) since total elements equal n. Iterating buckets from max frequency down is also O(n) in total.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   All steps combined remain linear in n [OK]

Hint: Bucket sort avoids sorting unique keys explicitly [OK]

Common Mistakes:

• Confusing with sorting complexity
• Assuming heap operations dominate

4. Suppose you want to find the kth largest element in an array where elements can be repeated and you want to find the kth largest unique element instead. Which modification to the Quickselect approach is correct?

hard

A. Use a min-heap of size k to store unique elements only, ignoring duplicates during insertion.

B. Run Quickselect as usual and then scan left and right to skip duplicates until kth unique is found.

C. Sort the array fully and iterate from largest to smallest counting unique elements until kth unique is reached.

D. Modify partition to skip duplicates and recurse only on unique elements.

Solution

1. Step 1: Understand uniqueness constraint

   Quickselect partitions by value but does not handle uniqueness inherently.

2. Step 2: Evaluate modifications

   Partial scanning or modifying partition is complex and error-prone; min-heap requires extra checks.

3. Step 3: Choose reliable approach

   Sorting fully and counting unique elements is straightforward and guarantees correctness.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Full sort enables unique counting easily [OK]

Hint: Uniqueness requires full sort or extra data structures [OK]

Common Mistakes:

• Assuming Quickselect handles uniqueness
• Trying to modify partition without correctness
• Ignoring duplicates in heap approach

5. Suppose the problem changes: the matrix is no longer sorted by columns, only rows are sorted, and you still need to find the kth smallest element. Which approach is the most suitable to solve this variant efficiently?

hard

A. Use binary search on the value range with the same counting method as before.

B. Use a greedy approach picking the smallest element from each row repeatedly.

C. Flatten the matrix and sort all elements to find the kth smallest.

D. Use a min heap to merge the k sorted rows, extracting the kth smallest element.

Solution

1. Step 1: Understand changed constraints

   Only rows are sorted, columns are not sorted, so binary search counting on columns is invalid.

2. Step 2: Identify suitable approach

   Min heap merging k sorted lists (rows) efficiently finds kth smallest in O(k log n) time.

3. Step 3: Reject other approaches

   Binary search counting fails without column sorting; flattening is O(n² log n²); greedy is incorrect.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Min heap merge exploits row sorting without column sorting [OK]

Hint: Without column sorting, binary search counting fails [OK]

Common Mistakes:

• Trying binary search counting without column sorting
• Assuming greedy works