📌 Day 18: The Greedy Pattern (Amazon Interview Series)

Greedy algorithms are all about making locally optimal choices at each step, hoping to reach a globally optimal solution. Amazon frequently uses this pattern in scheduling, interval, and resource allocation problems.

---

🔑 When to Use the Greedy Pattern

Use Greedy when:

• A problem involves optimization (maximize/minimize something).
• The problem can be solved by sorting + local decision-making.
• Once a choice is made, it doesn’t need to be reconsidered (no backtracking).

---

📝 Problem 1: Activity Selection (Interval Scheduling)

👉 Amazon-style phrasing:
You are given n activities with start and end times. Select the maximum number of non-overlapping activities.

Java Solution

import java.util.*;

public class ActivitySelection {
    static class Interval {
        int start, end;
        Interval(int s, int e) { start = s; end = e; }
    }

    public static int maxActivities(List<Interval> activities) {
        activities.sort(Comparator.comparingInt(a -> a.end));
        int count = 0, lastEnd = -1;

        for (Interval act : activities) {
            if (act.start >= lastEnd) {
                count++;
                lastEnd = act.end;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        List<Interval> activities = Arrays.asList(
            new Interval(1, 3),
            new Interval(2, 4),
            new Interval(3, 5),
            new Interval(0, 6),
            new Interval(5, 7),
            new Interval(8, 9)
        );
        System.out.println(maxActivities(activities)); // Output: 4
    }
}

✅ Key Insight: Always pick the activity that finishes earliest.

---

📝 Problem 2: Minimum Number of Platforms (Railway Scheduling)

👉 Amazon-style phrasing:
Trains arrive and depart at different times. Find the minimum number of platforms required so that no train waits.

Java Solution

import java.util.*;

public class MinPlatforms {
    public static int findMinPlatforms(int[] arrivals, int[] departures) {
        Arrays.sort(arrivals);
        Arrays.sort(departures);

        int platforms = 0, maxPlatforms = 0;
        int i = 0, j = 0;

        while (i < arrivals.length && j < departures.length) {
            if (arrivals[i] <= departures[j]) {
                platforms++;
                i++;
            } else {
                platforms--;
                j++;
            }
            maxPlatforms = Math.max(maxPlatforms, platforms);
        }
        return maxPlatforms;
    }

    public static void main(String[] args) {
        int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
        int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
        System.out.println(findMinPlatforms(arrivals, departures)); // Output: 3
    }
}

✅ Key Insight: Use sorted order of arrivals and departures to greedily track overlaps.

---

📝 Problem 3: Minimum Number of Coins (Coin Change)

👉 Amazon-style phrasing:
You are given coin denominations and an amount. Find the minimum number of coins required to make that amount.

⚠️ Note: This greedy works only for denominations like 1, 2, 5, 10, 20… (canonical coin system). For arbitrary denominations, use DP.

Java Solution

import java.util.*;

public class CoinChangeGreedy {
    public static int minCoins(int[] coins, int amount) {
        Arrays.sort(coins);
        int count = 0;
        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] coins = {1, 2, 5, 10, 20, 50, 100};
        int amount = 93;
        System.out.println(minCoins(coins, amount)); // Output: 5 (50+20+20+2+1)
    }
}

✅ Key Insight: Always take the largest denomination possible first.

---

🎯 Amazon Variations of Greedy Problems

• Job Scheduling with Deadlines → maximize profit with deadlines.
• Fractional Knapsack → take max profit-to-weight ratio first.
• Gas Station Refueling → minimize refueling stops.
• Rope Cutting → maximize product by cutting ropes optimally.

---

🏆 Key Takeaways

• Greedy = sort + local choice.
• Works best when local optimum = global optimum.
• Amazon asks these to test if you can recognize when DP is overkill and greedy suffices.

---

📅 Next in the series (Day 19):
👉 Backtracking Pattern – solving constraint problems like N-Queens, Word Search, and Subset Generation.

---