Maximum CPU Load (Peak Overlap)

📋

Maximum CPU Load (Peak Overlap)

Edge cases:

</>

IDE

def find_max_cpu_load(jobs: list[list[int]]) -> int:public int findMaxCpuLoad(int[][] jobs)int findMaxCpuLoad(vector<vector<int>>& jobs)function findMaxCpuLoad(jobs)

def find_max_cpu_load(jobs):
    # Write your solution here
    pass

class Solution {
    public int findMaxCpuLoad(int[][] jobs) {
        // Write your solution here
        return 0;
    }
}

#include <vector>
using namespace std;

int findMaxCpuLoad(vector<vector<int>>& jobs) {
    // Write your solution here
    return 0;
}

function findMaxCpuLoad(jobs) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Sum of max loads of individual jobs without considering overlapsCode returns sum of all loads instead of max concurrent load.✅ Use a min-heap to track active jobs and sum their loads at each step, updating max load accordingly.

Wrong: Max load equals max single job load even when jobs overlapCode ignores overlaps and returns max load of any single job only.✅ Check for overlaps by comparing start and end times and sum loads of overlapping jobs.

Wrong: Incorrect max load due to treating touching intervals as overlappingCode uses <= or >= instead of < or > for overlap checks.✅ Use strict inequalities (start < end) to determine overlaps.

Wrong: Code crashes or returns non-zero on empty inputNo check for empty input list.✅ Add a guard clause to return 0 if jobs list is empty.

Wrong: TLE on large inputsBrute force O(n^2) approach used.✅ Implement sorting + min-heap or sweep line algorithm with O(n log n) complexity.

✓

Test Cases

Try testing your code with empty and single job inputs to ensure base cases are handled.

Check if your code correctly sums all overlapping jobs and handles edge overlaps precisely.

Optimize your solution to O(n log n) using sorting and a min-heap or sweep line to pass large inputs.

t1_01basic

Input{"jobs":[[1,4,3],[2,5,4],[7,9,6]]}

Expected7

⏱ Performance - must finish in 2000ms

Jobs 1 and 2 overlap between time 2 and 4, total load = 3 + 4 = 7. Job 3 does not overlap with others.

💡 Consider sorting jobs by start time and tracking overlapping jobs.

💡 Use a min-heap to remove jobs that ended before the current job starts.

💡 At each job, sum loads of overlapping jobs in the heap and update max load.

Why it failed: Incorrect output means overlapping intervals not handled correctly; fix by maintaining a min-heap of active jobs and summing their loads properly.

✓ Correctly handles overlapping intervals and computes max load.

t1_02basic

Input{"jobs":[[1,3,5],[3,6,7],[6,9,2]]}

Expected7

⏱ Performance - must finish in 2000ms

No jobs overlap; max load is max single job load = 7 from job 2.

💡 Check if jobs overlap by comparing start and end times.

💡 If no overlap, max load is max load among all jobs.

💡 Ensure your code handles edge where end time equals next start time as non-overlapping.

Why it failed: Failing this test means your code treats touching intervals as overlapping; fix by using strict inequality for overlap checks.

✓ Correctly distinguishes overlapping and non-overlapping intervals.

t2_01edge

Input{"jobs":[]}

Expected0

⏱ Performance - must finish in 2000ms

Empty input means no jobs, so max load is 0.

💡 Consider what happens if input list is empty.

💡 Your code should handle zero-length input gracefully.

💡 Return 0 immediately if no jobs are present.

Why it failed: Code crashes or returns non-zero on empty input; fix by adding a check for empty job list and return 0.

✓ Handles empty input correctly by returning 0.

t2_02edge

Input{"jobs":[[5,10,8]]}

Expected8

⏱ Performance - must finish in 2000ms

Single job only; max load equals that job's load.

💡 Test with only one job to verify base case.

💡 Your code should return the load of the single job.

💡 Avoid unnecessary loops or heap operations for single job.

Why it failed: Fails single job test means code does not handle base case; fix by returning job load if only one job.

✓ Correctly returns load for single job.

t2_03edge

Input{"jobs":[[1,5,2],[1,5,3],[1,5,4]]}

Expected9

⏱ Performance - must finish in 2000ms

All jobs fully overlap; max load is sum of all loads = 2+3+4=9.

💡 Check if your code sums loads correctly when all jobs overlap.

💡 Ensure your heap or sweep line accumulates all concurrent loads.

💡 Sum all loads active at the same time to get max load.

Why it failed: Fails full overlap test means loads not summed correctly; fix by summing all active jobs' loads at overlap.

✓ Correctly sums loads for fully overlapping jobs.

t2_04edge

Input{"jobs":[[1,1,5],[1,1,10],[1,1,3]]}

Expected10

⏱ Performance - must finish in 2000ms

Jobs with same start and end times; all loads count at that instant, sum = 5+10+3=18.

💡 Check how your code handles jobs with zero-length intervals.

💡 Ensure loads are counted even if start equals end time.

💡 Sum all loads for jobs starting and ending at the same time.

Why it failed: Fails to count loads for zero-length intervals; fix by including jobs where start == end in load calculation.

✓ Correctly counts loads for jobs with same start and end times.

t3_01corner

Input{"jobs":[[1,4,3],[2,6,5],[4,7,4]]}

Expected9

⏱ Performance - must finish in 2000ms

Jobs 1 and 2 overlap (load 8), jobs 2 and 3 overlap (load 9), max load is 9 during overlap of jobs 2 and 3.

💡 Check if your code updates max load after removing ended jobs.

💡 Beware of off-by-one errors in overlap intervals.

💡 Use a min-heap or sweep line to track active jobs and update max load correctly.

Why it failed: Incorrect max load means off-by-one or event ordering bug; fix by removing jobs that ended before current start time before summing loads.

✓ Correctly handles overlapping intervals with proper event ordering.

t3_02corner

Input{"jobs":[[1,3,4],[2,5,6],[3,6,5]]}

Expected11

⏱ Performance - must finish in 2000ms

Jobs 1 and 2 overlap (load 10), jobs 2 and 3 overlap (load 11), max load is 11 during overlap of jobs 2 and 3.

💡 Test if your code treats end time equal to start time as overlapping or not.

💡 Use strict inequality for overlap checks to avoid counting non-overlapping jobs.

💡 Update max load after adjusting active jobs at each event.

Why it failed: Fails due to treating touching intervals as overlapping; fix by using strict inequality (start < end) for overlaps.

✓ Correctly distinguishes overlapping intervals with proper inequality.

t3_03corner

Input{"jobs":[[1,10,2],[2,3,10],[4,5,10],[6,7,10],[8,9,10]]}

Expected22

⏱ Performance - must finish in 2000ms

Job 1 overlaps with all small jobs; max load is 2 + 10 = 12 at each small job, max is 22 when job 1 overlaps with two small jobs (e.g. jobs 2 and 3).

💡 Beware of greedy approach that only sums max load of one overlapping job.

💡 Use a min-heap or sweep line to track all overlapping jobs simultaneously.

💡 Sum all active jobs' loads to find max load.

Why it failed: Fails due to greedy approach summing only max load job; fix by summing all overlapping jobs' loads.

✓ Correctly sums loads of all overlapping jobs.

t4_01performance

Input{"jobs":[[0,1000,10000],[1000,2000,10000],[2000,3000,10000],[3000,4000,10000],[4000,5000,10000],[5000,6000,10000],[6000,7000,10000],[7000,8000,10000],[8000,9000,10000],[9000,10000,10000],[10000,11000,10000],[11000,12000,10000],[12000,13000,10000],[13000,14000,10000],[14000,15000,10000],[15000,16000,10000],[16000,17000,10000],[17000,18000,10000],[18000,19000,10000],[19000,20000,10000],[20000,21000,10000],[21000,22000,10000],[22000,23000,10000],[23000,24000,10000],[24000,25000,10000],[25000,26000,10000],[26000,27000,10000],[27000,28000,10000],[28000,29000,10000],[29000,30000,10000],[30000,31000,10000],[31000,32000,10000],[32000,33000,10000],[33000,34000,10000],[34000,35000,10000],[35000,36000,10000],[36000,37000,10000],[37000,38000,10000],[38000,39000,10000],[39000,40000,10000],[40000,41000,10000],[41000,42000,10000],[42000,43000,10000],[43000,44000,10000],[44000,45000,10000],[45000,46000,10000],[46000,47000,10000],[47000,48000,10000],[48000,49000,10000],[49000,50000,10000],[50000,51000,10000],[51000,52000,10000],[52000,53000,10000],[53000,54000,10000],[54000,55000,10000],[55000,56000,10000],[56000,57000,10000],[57000,58000,10000],[58000,59000,10000],[59000,60000,10000],[60000,61000,10000],[61000,62000,10000],[62000,63000,10000],[63000,64000,10000],[64000,65000,10000],[65000,66000,10000],[66000,67000,10000],[67000,68000,10000],[68000,69000,10000],[69000,70000,10000],[70000,71000,10000],[71000,72000,10000],[72000,73000,10000],[73000,74000,10000],[74000,75000,10000],[75000,76000,10000],[76000,77000,10000],[77000,78000,10000],[78000,79000,10000],[79000,80000,10000],[80000,81000,10000],[81000,82000,10000],[82000,83000,10000],[83000,84000,10000],[84000,85000,10000],[85000,86000,10000],[86000,87000,10000],[87000,88000,10000],[88000,89000,10000],[89000,90000,10000],[90000,91000,10000],[91000,92000,10000],[92000,93000,10000],[93000,94000,10000],[94000,95000,10000],[95000,96000,10000],[96000,97000,10000],[97000,98000,10000],[98000,99000,10000],[99000,100000,10000]]}

Expectednull

⏱ Performance - must finish in 2000ms

n=100 jobs with fixed length intervals, O(n log n) solution must complete within 2 seconds.

💡 Use sorting and a min-heap to track overlapping jobs efficiently.

💡 Avoid O(n^2) brute force which will time out.

💡 Implement sweep line or heap-based approach for O(n log n) complexity.

Why it failed: TLE indicates brute force O(n^2) approach; fix by using sorting + min-heap or sweep line algorithm with O(n log n) complexity.

✓ Efficient O(n log n) solution passes performance test.

Practice

1. You are given a list of words and need to find the top k words that appear most frequently, with ties broken by lexicographical order. Which algorithmic approach guarantees an optimal solution in terms of time complexity?

easy

A. Sort all unique words by frequency descending and lex order ascending, then pick top k

B. Use a dynamic programming approach to count frequencies and select top k

C. Use a greedy approach by repeatedly picking the most frequent word until k are chosen

D. Use bucket sort by frequency, then sort words lexicographically within each bucket, and collect top k

Solution

1. Step 1: Understand frequency distribution

   Counting frequencies is straightforward, but sorting all words fully costs O(n log n).

2. Step 2: Use bucket sort to group words by frequency

   Bucket sort groups words by frequency in O(n), then sorting lex order within buckets is efficient since buckets are smaller.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Bucket sort + lex sort within buckets achieves O(n) time [OK]

Hint: Bucket sort by frequency then lex sort is optimal [OK]

Common Mistakes:

• Assuming full sort is optimal
• Using DP for frequency counting
• Greedy without sorting fails tie-break

2. What is the time complexity of the pop() operation in the optimal frequency stack implementation that uses a max-heap keyed by frequency and timestamp, assuming n total operations?

medium

A. O(1) amortized, since the heap is balanced automatically

B. O(log n), due to heap pop operation on at most n elements

C. O(n), because frequencies must be recomputed on each pop

D. O(log k), where k is the number of distinct elements

Solution

1. Step 1: Identify heap size and operations

   The heap stores one entry per push operation, so its size can be up to n.

2. Step 2: Analyze pop complexity

   Each pop calls heapq.heappop which takes O(log n) time in worst case. Frequency map updates are O(1).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Heap pop dominates time complexity, so O(log n) per pop [OK]

Hint: Heap pop is O(log n), not O(1) or O(n) [OK]

Common Mistakes:

• Assuming heap pop is O(1)
• Confusing frequency recomputation cost
• Assuming complexity depends on distinct elements only

3. Consider the following buggy Quickselect implementation. Which line contains the subtle bug that can cause incorrect results?

medium

A. Line 4: The comparison operator in the if condition inside partition

B. Line 7: The swap of nums[i] and nums[right]

C. Line 11: The base case check if left == right

D. Line 15: The recursive call when pivot_index < k

Solution

1. Step 1: Identify partition logic

   Partition should move elements greater than pivot to the left for kth largest.

2. Step 2: Locate bug

   The condition uses '<' instead of '>', reversing the order and breaking correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Incorrect comparison flips partition logic [OK]

Hint: Partition comparison must match desired order (greater for kth largest) [OK]

Common Mistakes:

• Using wrong comparison direction in partition
• Confusing base case with recursion
• Swapping wrong elements

4. Consider the following buggy code snippet for the minimum cost to hire K workers problem. Which line contains the subtle bug that causes incorrect results on some inputs?

import bisect

def mincostToHireWorkers(quality, wage, K):
    workers = sorted([(w/q, q) for q, w in zip(quality, wage)])
    qualities = []
    sum_quality = 0
    min_cost = float('inf')
    for ratio, q in workers:
        bisect.insort(qualities, q)
        sum_quality += q
        if len(qualities) > K:
            removed = qualities.pop(0)  # BUG: removes smallest quality instead of largest
            sum_quality -= removed
        if len(qualities) == K:
            cost = ratio * sum_quality
            if cost < min_cost:
                min_cost = cost
    return min_cost

medium

A. Line where qualities.pop(0) removes the smallest quality

B. Line where qualities are inserted using bisect.insort

C. Line where workers are sorted by ratio

D. Line where cost is calculated as ratio * sum_quality

Solution

1. Step 1: Identify the data structure usage

   qualities is a sorted list; bisect.insort inserts maintaining ascending order.

2. Step 2: Check removal logic when size exceeds K

   qualities.pop(0) removes the smallest quality, but we want to remove the largest quality to minimize sum_quality.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Removing smallest quality increases sum_quality, leading to incorrect cost [OK]

Hint: Remove largest quality, not smallest, to minimize sum [OK]

Common Mistakes:

• Removing smallest quality instead of largest
• Not updating min_cost when size == K
• Sorting workers incorrectly

5. Suppose the problem changes: now elements can be reused infinitely many times, and you want the top k frequent elements considering this reuse. Which modification to the optimal bucket sort approach correctly handles this scenario?

hard

A. Use a min-heap of size k to dynamically track frequencies as elements can be reused infinitely.

B. Modify frequency counting to consider reuse by multiplying counts, then bucket sort as usual.

C. No change needed; bucket sort works the same since frequencies are static counts.

D. Switch to a max-heap approach to handle infinite reuse frequencies efficiently.

Solution

1. Step 1: Understand infinite reuse impact

   Infinite reuse means frequencies are dynamic or unbounded, so static frequency counting and bucket sort no longer apply.

2. Step 2: Choose data structure for dynamic top k

   A min-heap of size k can maintain the top k elements dynamically as frequencies update, suitable for infinite reuse scenarios.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bucket sort relies on fixed frequencies; min-heap adapts to changing frequencies [OK]

Hint: Bucket sort assumes fixed frequencies; min-heap handles dynamic updates [OK]

Common Mistakes:

• Assuming bucket sort works unchanged
• Using max-heap which grows too large