Greedy Algorithms

Greedy algorithms make the locally optimal choice at each step, hoping for a globally optimal solution. Works when the problem has greedy choice property (local optimal leads to global optimal) and optimal substructure. Key patterns: activity selection, interval scheduling, Huffman coding. If greedy doesn't work, usually DP is the fallback.

Key Concepts

Deep Dive: When Greedy Works

Greedy works: Activity selection, coin change (standard denominations), fractional knapsack, Huffman coding, minimum spanning tree (Kruskal's/Prim's)

Greedy fails: 0/1 knapsack, longest path, coin change (arbitrary denominations) → use DP instead

Deep Dive: Interval Scheduling

Non-overlapping intervals (maximum activities):

public int maxNonOverlapping(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[1] - b[1]);  // Sort by end time
    int count = 1, end = intervals[0][1];
    for (int i = 1; i < intervals.length; i++) {
        if (intervals[i][0] >= end) {
            count++;
            end = intervals[i][1];
        }
    }
    return count;
}

Minimum number of intervals to remove:

public int eraseOverlapIntervals(int[][] intervals) {
    return intervals.length - maxNonOverlapping(intervals);
}

Deep Dive: Jump Game

// Can you reach the last index?
public boolean canJump(int[] nums) {
    int maxReach = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i > maxReach) return false;
        maxReach = Math.max(maxReach, i + nums[i]);
    }
    return true;
}

Common Interview Questions

• Jump Game I and II
• Non-overlapping Intervals
• Meeting Rooms II (min rooms needed)
• Gas Station
• Assign Cookies
• Partition Labels
• Task Scheduler