Greedy Fundamentals

🍕 Greedy Algorithms: The “Biggest Slice First” Strategy

The Universal Analogy: The Pizza Party Problem

Imagine you’re at a pizza party with your friends. The pizza is cut into slices of different sizes. You’re really hungry, and you want to eat as much as possible. What do you do?

You grab the BIGGEST slice first!

Then the next biggest. Then the next.

That’s it. That’s a greedy algorithm. You make the best choice RIGHT NOW without worrying about what comes later.

🧠 Greedy Algorithm Fundamentals

What Makes an Algorithm “Greedy”?

A greedy algorithm is like a hungry person at a buffet:

1. Look at your options
2. Pick the best one RIGHT NOW
3. Never look back or change your mind
4. Repeat until you’re done

The Golden Rule

“Always make the locally optimal choice and hope it leads to a globally optimal solution.”

When Does Greedy Work?

Think of it like building with LEGO blocks:

✅ Works when: Each good choice leads to more good choices ❌ Fails when: The best choice now blocks better choices later

# The Greedy Pattern
def greedy_solve(problem):
    solution = []
    while problem_not_solved:
        # Find the best choice RIGHT NOW
        best = find_best_option()
        # Take it!
        solution.append(best)
        # Remove it from options
        update_problem()
    return solution

Simple Example: Making Change

You need to give ₹93 in change using the fewest coins. Coins available: ₹50, ₹20, ₹10, ₹5, ₹2, ₹1

Greedy approach:

1. Use the BIGGEST coin that fits: ₹50 → Left: ₹43
2. Next biggest that fits: ₹20 → Left: ₹23
3. Next: ₹20 → Left: ₹3
4. Next: ₹2 → Left: ₹1
5. Finally: ₹1 → Done!

Answer: ₹50 + ₹20 + ₹20 + ₹2 + ₹1 = 5 coins

🗓️ Activity Selection Problem

The Story

You’re a busy kid with a PACKED Saturday! You want to do as many fun activities as possible.

Problem: Some activities overlap! You can’t swim AND watch movies at the same time.

The Greedy Trick

Always pick the activity that ENDS EARLIEST!

Why? Because it frees up your time for more activities later.

def activity_selection(activities):
    # Sort by end time (earliest first)
    activities.sort(key=lambda x: x[1])

    selected = [activities[0]]
    last_end = activities[0][1]

    for start, end in activities[1:]:
        # If this activity starts after
        # the last one ends, take it!
        if start >= last_end:
            selected.append((start, end))
            last_end = end

    return selected

Walking Through Our Example

1. Sort by end time: Gaming(12), Swimming(11), Movies(1PM), Pizza(2PM), Soccer(4PM)
2. Pick Gaming (ends at 12)
3. Skip Swimming (overlaps)
4. Skip Movies (overlaps)
5. Pick Pizza Party (starts at 12, ends at 2)
6. Pick Soccer (starts at 2, ends at 4)

Result: Gaming → Pizza Party → Soccer (3 activities!)

🏢 Meeting Rooms Problem

The Story

You’re the boss of a company. Everyone wants to use the conference room today! How many rooms do you need so everyone can have their meeting?

The Greedy Insight

Think of it like a restaurant:

• When someone arrives → they need a table
• When someone leaves → that table is free again

Track the MAXIMUM number of overlapping meetings!

def min_meeting_rooms(meetings):
    events = []
    for start, end in meetings:
        events.append((start, 'arrive'))
        events.append((end, 'leave'))

    # Sort: if same time, 'leave' before 'arrive'
    events.sort(key=lambda x: (x[0], x[1] == 'arrive'))

    rooms_needed = 0
    current_rooms = 0

    for time, action in events:
        if action == 'arrive':
            current_rooms += 1
            rooms_needed = max(rooms_needed, current_rooms)
        else:
            current_rooms -= 1

    return rooms_needed

Our Example

• 9:00 → Team A arrives (1 room)
• 9:00 → Team B arrives (2 rooms) ← Peak!
• 10:00 → Team A leaves (1 room)
• 10:00 → Team C arrives (2 rooms)
• 11:00 → Team B leaves (1 room)
• 11:00 → Team C leaves (0 rooms)
• 11:00 → Team D arrives (1 room)
• 12:00 → Team D leaves (0 rooms)

Answer: You need 2 rooms!

📅 Interval Scheduling

The Story

This is like Activity Selection’s big sibling. You have jobs with start and end times, but each job has a different value (money you earn).

Two Flavors

Flavor 1: Maximum Jobs (Classic Greedy) → Pick earliest ending times → Same as Activity Selection!

Flavor 2: Maximum Value (Weighted) → This needs Dynamic Programming (greedy alone won’t work!) → But we can still use greedy thinking as a starting point

# Maximum non-overlapping intervals
def max_intervals(intervals):
    intervals.sort(key=lambda x: x[1])

    count = 0
    last_end = float('-inf')

    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end

    return count

🦘 Jump Game

The Story

You’re a frog on lily pads! Each lily pad has a number that tells you the maximum distance you can jump from there.

Can you reach the last lily pad?

Lily pads: [2, 3, 1, 1, 4]
           ↑
         Start

• From pad 0 (value 2): Jump up to 2 pads
• From pad 1 (value 3): Jump up to 3 pads
• And so on…

The Greedy Magic

Track how FAR you can possibly reach!

At each step, update your “farthest reachable” position.

def can_jump(nums):
    farthest = 0

    for i in range(len(nums)):
        # Can we even reach this pad?
        if i > farthest:
            return False

        # Update farthest we can reach
        farthest = max(farthest, i + nums[i])

        # Did we reach the end?
        if farthest >= len(nums) - 1:
            return True

    return True

Walking Through [2, 3, 1, 1, 4]

At position 1, farthest = 4, which reaches the end!

Answer: Yes, we can reach the last lily pad!

Jump Game II: Minimum Jumps

What’s the fewest jumps to reach the end?

def min_jumps(nums):
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])

        # Time to make a jump!
        if i == current_end:
            jumps += 1
            current_end = farthest

    return jumps

⛽ Gas Station Problem

The Story

You’re driving a car in a circle. There are gas stations along the way. Each station:

• Gives you some gas
• The road to the NEXT station costs some gas

Can you complete the circle? If yes, where should you start?

Stations:  A    B    C    D
Gas:       4    6    1    2
Cost:      3    4    5    1

The Greedy Secret

If the total gas ≥ total cost, a solution EXISTS!

And the trick: Start right AFTER the point where you ran out of gas!

def can_complete_circuit(gas, cost):
    # First check: Is it even possible?
    if sum(gas) < sum(cost):
        return -1

    start = 0
    tank = 0

    for i in range(len(gas)):
        tank += gas[i] - cost[i]

        # Ran out of gas!
        if tank < 0:
            # Start from the NEXT station
            start = i + 1
            tank = 0

    return start

Why Does This Work?

Imagine you’re walking and you fall into a hole at station C.

Everything BEFORE station C wasn’t strong enough to carry you through.

So start AFTER the hole (at station D)!

If total gas ≥ total cost, starting from D will definitely work.

📋 Task Scheduler

The Story

You’re a chef with orders to make. Each order takes the same time, but you can’t make the same dish twice in a row (the pan needs to cool down!).

Orders: A, A, A, B, B, C Cooldown: 2 (wait 2 other tasks before repeating)

The Greedy Strategy

Always cook the dish you have the MOST of!

Why? The dish with most copies is the “bottleneck.” Handle it first!

from collections import Counter

def least_interval(tasks, n):
    counts = Counter(tasks)
    max_count = max(counts.values())

    # How many tasks have the max count?
    max_count_tasks = sum(
        1 for c in counts.values()
        if c == max_count
    )

    # Formula: frame-based calculation
    intervals = (max_count - 1) * (n + 1) + max_count_tasks

    # At minimum, we need len(tasks) intervals
    return max(intervals, len(tasks))

Visual Example

Tasks: A, A, A, B, B, C Cooldown n = 2

Building the schedule:

A _ _ A _ _ A
  ↓ ↓   ↓ ↓
A B C A B _ A

We have 3 A’s, so we create 3 “frames” of size (n+1) = 3:

• Frame 1: A, B, C
• Frame 2: A, B, idle
• Frame 3: A

Total time: 8 units

The Magic Formula Explained

intervals = (max_count - 1) × (n + 1) + max_count_tasks
          = (3 - 1) × (2 + 1) + 1
          = 2 × 3 + 1
          = 7

But we have 6 tasks, so answer = max(7, 6) = 7

Wait, I said 8 earlier! Let me recount: A B C A B _ A = 7 slots. Yes, 7 is correct!

🎯 Summary: When to Use Greedy

The Greedy Checklist

✅ Does choosing the best NOW help the overall goal? ✅ Do I never need to “undo” a choice? ✅ Does sorting help identify the “best” choice?

If yes to all three → Greedy might work!

🚀 You’ve Got This!

Greedy algorithms are like life advice from a wise pizza lover:

“Don’t overthink it. Grab the best slice now. Keep grabbing. Be happy.”

Not every problem can be solved greedily, but when it works, it’s elegant, fast, and beautiful.

Now go forth and be greedy (algorithmically)! 🍕