Greedy Choice and Proof

Greedy algorithms make the locally best-looking choice and never revisit it. That is powerful only when you can prove the local choice is safe.

Safe Local Choice

A greedy choice is valid when any optimal solution can be transformed to include that choice without making the result worse. That proof shape is called an exchange argument.

Scenario: Rate-Limit Budget

An API gateway has limited retry budget. Choosing the cheapest recovery action first can be valid if every action has independent benefit and no future dependency. If actions unlock each other, greedy can fail and stateful optimization may be required.

Same Pattern in Java, Python, and JavaScript

Activity selection: choose the meeting that ends earliest, then repeat among compatible meetings.

import java.util.*;

class ActivitySelection {
    static int maxMeetings(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int count = 0, end = Integer.MIN_VALUE;
        for (int[] in : intervals) {
            if (in[0] >= end) { count++; end = in[1]; }
        }
        return count;
    }
}

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return the maximum number of non-overlapping intervals.
• Return whether the last index is reachable.
• Return a station index that completes the circuit, or -1.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class ActivitySelection {
    static int maxMeetings(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int count = 0, end = Integer.MIN_VALUE;
        for (int[] in : intervals) {
            if (in[0] >= end) { count++; end = in[1]; }
        }
        return count;
    }
}

class JumpGame { static boolean canJump(int[] nums) { int farthest = 0; for (int i = 0; i < nums.length; i++) { if (i > farthest) return false; farthest = Math.max(farthest, i + nums[i]); } return true; } }

class GasStation { static int canCompleteCircuit(int[] gas, int[] cost) { int total = 0, tank = 0, start = 0; for (int i = 0; i < gas.length; i++) { int diff = gas[i] - cost[i]; total += diff; tank += diff; if (tank < 0) { start = i + 1; tank = 0; } } return total >= 0 ? start : -1; } }

Solved modelWorked Interview Answer

Select the maximum number of non-overlapping meetings. Sort by finish time. The earliest finishing compatible meeting leaves the most room for all future choices, which is the exchange argument.

import java.util.*;

class ActivitySelection {
    static int maxMeetings(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int count = 0, end = Integer.MIN_VALUE;
        for (int[] in : intervals) {
            if (in[0] >= end) { count++; end = in[1]; }
        }
        return count;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Using greedy without proof.
• Sorting by intuitive but unsafe keys.
• Confusing local optimum with global optimum.
• Using greedy for 0/1 choices that need DP.
• Not stating exchange argument.

Execution guardrailQuick-Start Checklist

• Name local choice.
• State invariant.
• Prove exchange safety.
• Show progress.
• Handle ties.
• State complexity.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice activity selection, jump game, gas station, and task scheduler.
• Compare greedy with DP on knapsack variants.
• Write proof before code.