Greedy Fundamentals

🍪 The Cookie Monster’s Guide to Greedy Algorithms

Imagine you’re a cookie monster. You see a pile of cookies. What do you do? You grab the BIGGEST cookie first! That’s exactly how greedy algorithms work.

🎯 What is a Greedy Algorithm?

Think of a greedy algorithm like a hungry kid at a buffet. At each step, they pick what looks BEST right now, without worrying about later.

The Magic Rule

Always pick the best choice available RIGHT NOW.

Simple Example:

• You have coins: 25¢, 10¢, 5¢, 1¢
• You need to give 36¢ change
• Greedy approach: Pick biggest coin that fits!
  • 25¢ ✓ (11¢ left)
  • 10¢ ✓ (1¢ left)
  • 1¢ ✓ (Done!)
• Result: 3 coins!

When Does Greedy Work?

graph TD
    A["🤔 Can I make a choice?"] --> B{Is local best = global best?}
    B -->|Yes| C["✅ Use Greedy!"]
    B -->|No| D["❌ Try DP or other"]

Greedy works when:

1. Each small choice leads to the big answer
2. You never need to “go back” and change your mind

🎬 Activity Selection Problem

The Story

You’re a TV remote. You have a list of shows with start and end times. You want to watch as MANY complete shows as possible!

The Trick

Always pick the show that ENDS earliest!

Why? Because it frees up time for more shows later!

Example:

Step by step:

1. Sort by end time ✓
2. Pick A (ends at 3) ✓
3. Skip B (starts at 2, conflicts with A)
4. Pick C (starts at 4, after A ends) ✓
5. Pick D (starts at 6, after C ends) ✓

Result: 3 shows! (A, C, D)

Java Code

// Sort activities by end time
Arrays.sort(activities,
  (a, b) -> a.end - b.end);

int count = 1;
int lastEnd = activities[0].end;

for (int i = 1; i < n; i++) {
  if (activities[i].start >= lastEnd) {
    count++;
    lastEnd = activities[i].end;
  }
}

🏢 Meeting Rooms Problem

The Story

You’re a building manager. People want to book rooms for meetings. How many rooms do you need so NO meetings overlap?

The Trick

Count how many meetings happen at the same time!

The maximum overlap = rooms needed.

Example:

graph TD
    A["9:00 - Two meetings start"] --> B["Need 2 rooms"]
    B --> C["10:00 - A ends, C starts"]
    C --> D["Still need 2 rooms max"]

Answer: 2 rooms needed!

Java Code

// Separate start and end times
Arrays.sort(starts);
Arrays.sort(ends);

int rooms = 0, maxRooms = 0;
int i = 0, j = 0;

while (i < n) {
  if (starts[i] < ends[j]) {
    rooms++;  // Meeting started
    i++;
  } else {
    rooms--;  // Meeting ended
    j++;
  }
  maxRooms = Math.max(maxRooms, rooms);
}

📅 Interval Scheduling

The Story

You’re a babysitter with many families calling. Each family needs you for specific hours. You want to help as MANY families as possible!

Same as Activity Selection!

Pick the job that ends earliest!

Example:

Sorted by end: Jones(1-4), Smith(2-6), Brown(5-8)

1. Pick Jones (1-4) ✓
2. Skip Smith (overlaps with Jones)
3. Pick Brown (5-8) ✓

Result: 2 families helped!

🦘 Jump Game

The Story

You’re a frog on lily pads. Each pad shows how FAR you can jump. Can you reach the last pad?

The Trick

Track the FARTHEST pad you can reach!

Example: [2, 3, 1, 1, 4]

graph LR
    A["Pad 0: Jump 2"] --> B["Can reach pad 2"]
    B --> C["Pad 1: Jump 3"]
    C --> D["Can reach pad 4!"]
    D --> E["✅ SUCCESS!"]

Step by step:

• Pad 0: Can jump 2 → reach up to index 2
• Pad 1: Can jump 3 → reach up to index 4
• Index 4 is the end! ✓

Java Code

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;

⛽ Gas Station Problem

The Story

You’re driving a car around a circular track. Each station gives you gas, but driving to the next costs gas. Can you complete the loop?

The Trick

If total gas ≥ total cost, a solution EXISTS!

Start from where you first stop running out!

Example:

Finding the start:

• Total gas: 15
• Total cost: 15
• Solution exists! ✓

Try from station 3:

• 3→4: Have 4, need 1 ✓
• 4→0: Have 4+5=9, need 2 ✓
• Continue… Success!

Java Code

int totalGas = 0, currentGas = 0;
int startStation = 0;

for (int i = 0; i < n; i++) {
  totalGas += gas[i] - cost[i];
  currentGas += gas[i] - cost[i];

  if (currentGas < 0) {
    startStation = i + 1;
    currentGas = 0;
  }
}
return totalGas >= 0 ? startStation : -1;

⏰ Task Scheduler

The Story

You’re a CPU running tasks. Same tasks need a “cooldown” break between them. What’s the MINIMUM time to finish all tasks?

The Trick

Schedule the MOST FREQUENT task first!

Fill gaps with other tasks or idle time.

Example: Tasks: [A, A, A, B, B, B], Cooldown: 2

Without strategy: A _ _ A _ _ A B B B = 10 slots
With greedy:      A B _ A B _ A B = 8 slots

Visual Pattern

graph TD
    A["Count each task"] --> B["Find max frequency"]
    B --> C["Create slots: max-1 groups"]
    C --> D["Fill gaps with other tasks"]
    D --> E["Add idle if needed"]

Java Code

int[] freq = new int[26];
for (char c : tasks) freq[c - 'A']++;

int maxFreq = Arrays.stream(freq).max()
                    .getAsInt();
int maxCount = 0;
for (int f : freq)
  if (f == maxFreq) maxCount++;

int slots = (maxFreq - 1) * (n + 1)
            + maxCount;
return Math.max(tasks.length, slots);

🎁 Summary: The Greedy Mindset

Remember! 🧠

graph TD
    A["🍪 Be the Cookie Monster"] --> B["Always grab the BEST choice NOW"]
    B --> C[Don't look back]
    C --> D["Trust the greedy path"]
    D --> E["✅ Optimal solution!"]

The Greedy Promise:

If picking the best NOW always leads to the best LATER, greedy wins!

Now go forth and be greedy… in algorithms only! 🚀