Advanced Greedy: Jump Games, Assignments, and Scheduling

The Jump Game Series

Jump Game problems are classic greedy exercises that require maintaining a dynamic "reachable horizon."

Jump Game I: Can Reach End? (LeetCode 55)

Given an array of maximum jump lengths, determine if you can reach the last index starting from index 0.

Greedy Logic: Maintain the farthest index reachable so far (maxReach). If you ever find yourself at an index $i > maxReach$, it means you can never reach $i$ or anything beyond it.

public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        // If current index is beyond what we can reach, fail
        if (i > maxReach) return false;
        // Grease the horizon with the current jump potential
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

Jump Game II: Minimum Step Count (LeetCode 45)

Assuming the last index is always reachable, find the minimum number of jumps to get there.

Greedy Logic: "Don't jump until you have to." When you hit the boundary of your current jump range (curEnd), you must jump. At that moment, you choose the next boundary to be the farthest point possible (farthest) that you could have reached during your previous jump's traversal.

public int jump(int[] nums) {
    int jumps = 0;
    int curEnd = 0;   // The boundary of the current jump
    int farthest = 0; // The farthest we can reach in the NEXT jump
    
    // We stop at n-1 because if we are currently at or past n-1, 
    // we don't need another jump.
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == curEnd) {
            jumps++;
            curEnd = farthest;
        }
    }
    return jumps;
}

Candy Assignment (LeetCode 135)

There are $n$ children standing in a line. Each child has a rating. You must assign candies such that:

1. Each child has at least one candy.
2. Children with a higher rating than their neighbors get more candies.

Greedy Strategy: Satisfy the local constraints in two independent passes.

1. Left-to-Right: If ratings[i] > ratings[i-1], child $i$ gets candy[i-1] + 1 candies.
2. Right-to-Left: If ratings[i] > ratings[i+1], child $i$ gets max(candy[i], candy[i+1] + 1) candies.

public int candy(int[] ratings) {
    int n = ratings.length;
    int[] candies = new int[n];
    Arrays.fill(candies, 1);

    // Pass 1: Forward
    for (int i = 1; i < n; i++) {
        if (ratings[i] > ratings[i - 1]) candies[i] = candies[i - 1] + 1;
    }
    
    // Pass 2: Backward
    for (int i = n - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candies[i] = Math.max(candies[i], candies[i + 1] + 1);
        }
    }
    
    int total = 0;
    for (int c : candies) total += c;
    return total;
}

Gas Station (LeetCode 134)

A circular route with $N$ gas stations. gas[i] is the amount available at station $i$, and cost[i] is the cost to reach station $i+1$. Find the starting station to complete the circuit.

Insights:

1. If total gas < total cost, reaching the end is impossible.
2. If total gas $\ge$ total cost, a solution always exists.
3. If you start at $A$ and run out of gas at $B$, then no station between $A$ and $B$ (inclusive) can be a valid starting point.

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalTank = 0;
    int currentTank = 0;
    int startStation = 0;
    
    for (int i = 0; i < gas.length; i++) {
        int diff = gas[i] - cost[i];
        totalTank += diff;
        currentTank += diff;
        
        // If current path fails, reset start to next station
        if (currentTank < 0) {
            startStation = i + 1;
            currentTank = 0;
        }
    }
    return totalTank >= 0 ? startStation : -1;
}

Task Scheduler (LeetCode 621)

CPU tasks with a cooling interval $n$. Minimum time to complete all tasks.

Mathematical Logic:

• Let $M$ be the maximum frequency of any task.
• Let $K$ be the number of tasks that share this maximum frequency.
• The minimum time required is at least $(M - 1) \times (n + 1) + K$. This accounts for the $M-1$ full gaps punctuated by the $K$ high-frequency tasks in the last block.
• If the calculated slots are fewer than the actual number of tasks, the tasks themselves are the bottleneck, and the time is simply tasks.length.

public int leastInterval(char[] tasks, int n) {
    int[] freqs = new int[26];
    for (char c : tasks) freqs[c - 'A']++;
    Arrays.sort(freqs);
    
    int maxFreq = freqs[25];
    int maxCount = 0;
    for (int f : freqs) if (f == maxFreq) maxCount++;
    
    long parts = maxFreq - 1;
    long partLength = n + 1;
    long minDuration = parts * partLength + maxCount;
    
    return Math.max(tasks.length, (int) minDuration);
}

Summary Summary Table