Greedy Fundamentals

Greedy Algorithms: The Art of Making Smart Choices 🎯

The Cookie Monster’s Secret

Imagine you’re at a party with a HUGE plate of cookies. You’re hungry, and you want to eat as many as possible before your mom says “time to go!”

What do you do? You grab the biggest cookie first, right?

That’s Greedy Thinking — always pick the best thing available RIGHT NOW.

This simple idea solves incredibly complex problems in computer science!

What is a Greedy Algorithm?

A Greedy Algorithm makes the locally optimal choice at each step, hoping to find a global optimum.

Think of it like climbing a mountain in fog. You can’t see the top. So at every step, you just go uphill. Most of the time, this gets you to a peak!

The Greedy Recipe

1. Look at your choices
2. Pick the BEST one right now
3. Never look back
4. Repeat until done

When Does Greedy Work?

Greedy works perfectly when:

• Greedy Choice Property: A local best choice leads to a global best solution
• Optimal Substructure: The problem can be broken into smaller, similar problems

Simple Example: You have coins: 25¢, 10¢, 5¢, 1¢. Make 41¢ using fewest coins.

Greedy says: Take the biggest coin that fits!

• 25¢ (remaining: 16¢)
• 10¢ (remaining: 6¢)
• 5¢ (remaining: 1¢)
• 1¢ (remaining: 0¢)

Answer: 4 coins! ✅

Activity Selection: The Busy Kid Problem

The Story

Emma has ONE TV. Her favorite shows are:

Emma wants to watch as many COMPLETE shows as possible. What should she pick?

The Greedy Solution

Key Insight: Always pick the show that ends earliest!

Why? Because the earlier a show ends, the more time you have for other shows!

function activitySelection(activities) {
  // Sort by end time
  activities.sort((a, b) => a.end - b.end);

  let selected = [activities[0]];
  let lastEnd = activities[0].end;

  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastEnd) {
      selected.push(activities[i]);
      lastEnd = activities[i].end;
    }
  }
  return selected;
}

Emma’s Answer:

1. Cartoons (9:00-10:30) ✅
2. Sports (11:00-12:00) ✅

She watches 2 complete shows!

Meeting Rooms: How Many Rooms Do We Need?

The Story

You’re a school principal. Teachers need rooms for meetings:

How many rooms do you need so NO meetings overlap?

The Greedy Insight

Count the maximum number of meetings happening at the same time!

graph TD
    A["Sort all start & end times"] --> B["Walk through timeline"]
    B --> C{Is it a start?}
    C -->|Yes| D["+1 meeting happening"]
    C -->|No| E["-1 meeting ended"]
    D --> F["Track maximum"]
    E --> F

The Solution

function minMeetingRooms(meetings) {
  let events = [];

  for (let m of meetings) {
    events.push([m.start, 1]);  // +1 at start
    events.push([m.end, -1]);   // -1 at end
  }

  events.sort((a, b) =>
    a[0] - b[0] || a[1] - b[1]
  );

  let rooms = 0, maxRooms = 0;
  for (let [time, delta] of events) {
    rooms += delta;
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

Answer: 2 rooms!

At 9:30, both Math and English are happening = 2 rooms needed.

Interval Scheduling: Maximize Your Day

The Story

You’re a party DJ. Everyone wants you to play at their event:

You can only be at ONE place at a time. How do you play at the most events?

Same Magic, Same Trick!

Pick the event that ends earliest!

This is exactly like Activity Selection!

function maxEvents(events) {
  events.sort((a, b) => a.end - b.end);

  let count = 0;
  let lastEnd = 0;

  for (let event of events) {
    if (event.start >= lastEnd) {
      count++;
      lastEnd = event.end;
    }
  }
  return count;
}

Answer:

1. Birthday (1pm-4pm) ✅
2. Graduation (4pm-6pm) ✅

You play at 2 events!

Jump Game: Can You Reach the End?

The Story

You’re a frog on lily pads. Each pad has a number — the maximum jumps you can make from there.

Pads:  [2, 3, 1, 1, 4]
Index:  0  1  2  3  4

From pad 0: You can jump 1 or 2 pads (max 2) Goal: Reach the last pad!

The Greedy Approach

Track the farthest pad you can reach.

If at any point your current position is beyond what you can reach… you’re stuck!

graph TD
    A["Start at pad 0"] --> B["Track farthest reachable"]
    B --> C["Move to next pad"]
    C --> D{Can I be here?}
    D -->|No| E["STUCK! Return false"]
    D -->|Yes| F["Update farthest"]
    F --> G{Reached end?}
    G -->|Yes| H["SUCCESS! Return true"]
    G -->|No| C

The Solution

function canJump(nums) {
  let farthest = 0;

  for (let i = 0; i < nums.length; i++) {
    if (i > farthest) return false;
    farthest = Math.max(farthest, i + nums[i]);
  }
  return true;
}

Example Walkthrough:

• Pad 0: farthest = max(0, 0+2) = 2
• Pad 1: farthest = max(2, 1+3) = 4 ✅
• Pad 4 is the end! SUCCESS!

Gas Station: The Road Trip Puzzle

The Story

You’re driving in a circle. There are gas stations along the way.

Question: Where should you START so you can complete the loop?

The Greedy Insight

If you run out of gas going from station A to station B, then no station between A and B can be your starting point!

function canCompleteCircuit(gas, cost) {
  let totalGas = 0;
  let currentGas = 0;
  let startStation = 0;

  for (let i = 0; i < gas.length; i++) {
    let net = gas[i] - cost[i];
    totalGas += net;
    currentGas += net;

    if (currentGas < 0) {
      startStation = i + 1;
      currentGas = 0;
    }
  }

  return totalGas >= 0 ? startStation : -1;
}

Why This Works

• If totalGas >= 0, a solution EXISTS
• If we fail at station X, start after X
• We only need one pass through the stations!

Answer for our example: Start at station 3!

Task Scheduler: CPU Cooling Game

The Story

Your computer runs tasks: A, A, A, B, B, B

But there’s a rule: Same task needs a cooldown!

If cooldown = 2, you can’t run A again until 2 other tasks (or idle) happen.

Bad:  A → A → ... (NO! Need to wait!)
Good: A → B → idle → A → B → idle → A → B

Goal: Finish all tasks in minimum time.

The Greedy Strategy

Most frequent task controls everything!

graph TD
    A["Count each task"] --> B["Find max frequency"]
    B --> C["Calculate minimum slots"]
    C --> D["Fill gaps with other tasks"]
    D --> E["Answer: max of slots vs total tasks"]

The Solution

function leastInterval(tasks, n) {
  let freq = new Array(26).fill(0);

  for (let task of tasks) {
    freq[task.charCodeAt(0) - 65]++;
  }

  freq.sort((a, b) => b - a);
  let maxFreq = freq[0];

  // Count tasks with max frequency
  let maxCount = 0;
  for (let f of freq) {
    if (f === maxFreq) maxCount++;
  }

  // Minimum slots needed
  let slots = (maxFreq - 1) * (n + 1) + maxCount;

  return Math.max(slots, tasks.length);
}

Example: A,A,A,B,B,B with cooldown 2

• Max frequency = 3 (both A and B)
• Slots = (3-1) × (2+1) + 2 = 8

A → B → idle → A → B → idle → A → B
1   2    3     4   5    6     7   8

Answer: 8 time units!

The Greedy Mindset: Summary

graph TD
    A["🎯 GREEDY THINKING"] --> B["Sort by priority"]
    A --> C["Make local best choice"]
    A --> D["Never reconsider"]
    A --> E["Trust the process"]

    B --> F["Activity: Sort by END time"]
    B --> G["Rooms: Sort by START time"]
    B --> H["Tasks: Sort by FREQUENCY"]

When to Use Greedy

The 5 Problems at a Glance

Your Turn!

You now understand the greedy mindset. Remember:

“Don’t overthink. Take the best bite NOW.”

The cookie monster was right all along! 🍪

Next time you face a problem, ask yourself:

1. Can I sort this somehow?
2. What’s the best local choice?
3. Does picking it ruin anything?

If the answers are Yes, Clear, and No — go greedy! 🚀