Merge IntervalsHardO(n log n) time · O(n) space

Maximum CPU Load

Mahabharata — Bhima's Siege Engines — Peak War-Chariot Load at Any Moment

एककाले बहूनां योधानां बलं मिलति। तत् परमं भारं ज्ञात्वा नेता शक्तिं निर्णयेत्॥

*When the forces of many warriors converge at one moment — that peak load the commander must know to gauge his army's capacity.*

The Story

A list of jobs, each with `[start, end, cpuLoad]`. Multiple jobs can run simultaneously, their CPU loads adding up. Find the maximum CPU load at any single moment.

Bhima's war engineer needed to know the peak simultaneous weapon load on the chariot wheels. Unlike mi-5 (which counts rooms), here each job has a WEIGHT (cpu load), and we sum weights instead of counting.

The approach is identical to mi-5 but with weighted events: - Create event (time, +load) for each job START - Create event (time, -load) for each job END - Sort by time (end before start on ties) - Sweep: running sum += event load. Track maximum.

For `jobs = [[1,4,3],[2,5,4],[7,9,6]]`: Events: (1,+3),(2,+4),(4,-3),(5,-4),(7,+6),(9,-6) Sweep: 3, 7, 4, 0, 6, 0. Maximum = 7.

Bhima confirmed: at time point 2-4, both jobs run with combined load 3+4=7. That is the peak.

"The chariot wheels can handle load 7 — that is our design requirement," the engineer noted.

This is mi-5 with weights — the same event sweep pattern applied to a continuous resource allocation problem.

The Engineer's First Instinct

For each time point, sum all active jobs' CPU loads. O(max_time × n).

java

int maxCpuLoadBruteForce(int[][] jobs) {
    int maxTime = 0;
    for (int[] j : jobs) maxTime = Math.max(maxTime, j[1]);
    int maxLoad = 0;
    for (int t = 1; t <= maxTime; t++) {
        int load = 0;
        for (int[] j : jobs) if (j[0] <= t && t <= j[1]) load += j[2];
        maxLoad = Math.max(maxLoad, load);
    }
    return maxLoad;
}

Bhima's Weighted Sweep Wisdom

Identical to mi-5 but weighted. Create (time, +load) for start and (time, -load) for end. Sort (end events first on ties). Sweep: running sum += load. Track maximum sum.

java

int maxCpuLoad(int[][] jobs) {
    List<int[]> events = new ArrayList<>();
    for (int[] j : jobs) {
        events.add(new int[]{j[0], j[2]});   // start: +load
        events.add(new int[]{j[1], -j[2]});  // end: -load
    }
    // Sort: by time; ties: end (-load) before start (+load) → sort by load ascending
    events.sort((a, b) -> a[0] != b[0] ? a[0]-b[0] : a[1]-b[1]);
    int load = 0, maxLoad = 0;
    for (int[] e : events) {
        load += e[1];
        maxLoad = Math.max(maxLoad, load);
    }
    return maxLoad;
}

Step-by-Step Walkthrough

jobs=[[6,7,10],[2,4,11],[8,12,15]]
Events: (2,+11),(4,-11),(6,+10),(7,-10),(8,+15),(12,-15)
Sweep: 11,0,10,0,15,0. Max=15.
Return 15 ✅ (jobs never overlap, max single load=15)

Deep Insight

**mi-5 vs mi-6:** - mi-5: each job has load=1 (count rooms needed) - mi-6: each job has a varying load (sum loads) Same algorithm, same time complexity.

**Min-heap alternative:** Sort by start. Min-heap of (end, load) pairs. For each job: pop all finished jobs (heap.peek().end <= job.start). Push current job. Track heap load sum maximum.

**Why end-before-start matters here too:** If a job ends at t=4 and another starts at t=4, the ending job's load should be subtracted before adding the new load. Otherwise we'd count both simultaneously and overcount.

Complexity Analysis

Approach	Time	Space	Note
Brute Force	O(n × max_time)	O(1)	Sum loads at each time point
Optimal	O(n log n)	O(n)	Sort 2n events + linear sweep

Pattern Recognition

✅ Maximum sum of active weighted intervals
✅ Event sweep with weights: +load at start, -load at end
✅ Same structure as mi-5 but sum instead of count
✅ Tie-break: end events before start events

**LeetCode Trigger Phrases:**
→ "maximum CPU load"
→ "peak resource usage" at any time
→ "weighted intervals" + maximum simultaneous sum

Bhagavad Gita 7.11

शक्तिः शक्तिमतां चाहं कामरागविवर्जितम्। धर्माविरुद्धो भूतेषु कामोऽस्मि भरतर्षभ॥

I am the strength of the strong, devoid of selfish desire and attachment. I am desire itself, O Arjuna, when it is not contrary to dharma.

Connection: The maximum CPU load represents the peak of combined strength — when multiple forces converge at a single moment. Like Krishna who is strength itself in the strong, the algorithm identifies the moment when cumulative power peaks. The event sweep is the unbiased observer: adding when jobs start, subtracting when they end, always tracking where true peak strength manifests.