Peak Server Load
MediumIntervals
Problem
A server runs batch jobs. Job i is [start, end, load]: it adds load units of CPU from time start until it finishes at end (half-open, [start, end)). A job that ends at t no longer uses the CPU at t.
Return the highest total load the server carries at any moment, or 0 if there are no jobs.
Example 1
- Input:
- jobs = [[1, 4, 3], [2, 6, 5], [5, 8, 2]]
- Output:
- 8
During [2, 4) the first two jobs run together: 3 + 5 = 8.
Example 2
- Input:
- jobs = [[1, 3, 4], [3, 5, 4]]
- Output:
- 4
The first job is done at 3, exactly when the second starts.
Constraints
- 0 ≤ jobs.length ≤ 10^5
- 0 ≤ start < end ≤ 10^9
- 1 ≤ load ≤ 10^4
Hint
Show the first hint
The load only changes when a job starts or ends. Think of those moments as events.
Walkthrough
How to approach it
01Clarify before coding
- Does a job count at its end time? No, ranges are half-open.
- Can loads differ? Yes, so counting overlapping jobs is not enough; sum their loads.
- Empty input? Return 0.
02Brute force
For every job start, add up the loads of all jobs running at that instant and keep the maximum.
Cost: O(n²) time: 10^10 for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.