Skip to content
Tutorials Center
My learning

Topics

Lesson 170 of 225 ยท Greedy Algorithms

Greedy Problems

Practice greedy algorithms in Python: fractional knapsack, jump game, gas station, candy, task scheduler and assign cookies, each with a brute force first.

You have seen the greedy idea: make the best-looking choice now, never look back, and hope the pile of local choices adds up to a global optimum. You have also seen it succeed in interval scheduling and Huffman coding. This lesson is a workout. Nine classic problems, each with a brute-force idea first, then a greedy rule, with a short argument for why the rule is safe.

Every greedy solution in this lesson follows the same recipe: find the right order (usually a sort), or the right running quantity (a best reach, a running balance), then make one pass. Learning to spot which of those two shapes a problem has is most of the skill.

When you meet a new problem, ask: "If I sort the input by some key, is there an obviously safe first move?" If you can name the key and defend the first move with a swap argument, you probably have a greedy solution.

Problem 1: Fractional knapsack

You have items, each with a value and a weight, and a bag with capacity W. You may take fractions of an item. Maximize the total value.

Unlike the 0/1 knapsack, you can cut items. That single freedom makes greedy correct: take items in order of value per unit of weight, best first, and cut the last one if it does not fit.

TEXT
items (value, weight):  A(60, 10)  B(100, 20)  C(120, 30)     capacity 50
value per weight:       A = 6      B = 5       C = 4

take all of A   (weight 10, value 60)   room left 40
take all of B   (weight 20, value 100)  room left 20
take 20/30 of C (value 80)              room left 0
total = 240

Why it works. Suppose an optimal answer uses some of a worse-ratio item while a better-ratio item is not fully taken. Swap a small piece of the worse item for the same weight of the better one: the value does not drop. Repeat until the best items are full. Because pieces are interchangeable at their ratio, nothing is lost.

Python Fractional knapsack

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time is O(n log n) for the sort, space O(n) for the sorted copy.

Do not reuse this greedy rule for the 0/1 version. With the same items and capacity 50, ratio-greedy takes A and B (value 160), but the best 0/1 choice is B and C (value 220). Without the freedom to cut, the swap argument breaks.

Problem 2: Jump game

You are given a list nums where nums[i] is the farthest you can jump forward from index i. You start at index 0. Can you reach the last index?

Brute force

Try every jump length from every reachable index, with recursion. Each index can branch into up to n jumps, so without memoization this is exponential.

Greedy

You do not need to know how to reach each index. You only need the farthest index reachable so far. Walk left to right, keep reach = max(reach, i + nums[i]), and if you ever stand on an index beyond reach, you are stuck.

TEXT
nums = [2, 3, 1, 1, 4]
i=0  reach = max(0, 0+2) = 2
i=1  reach = max(2, 1+3) = 4     reach >= last index (4): True
TEXT
nums = [3, 2, 1, 0, 4]
i=0  reach = 3
i=1  reach = 3
i=2  reach = 3
i=3  reach = 3
i=4  4 > reach, stuck: False

Every index up to reach is reachable (you can stop on any of them), which is why a single number summarizes everything.

Python Jump game: can you reach the end

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(1).

Jump game II: the fewest jumps

Now the end is always reachable, and you want the minimum number of jumps. Think of it as BFS in layers: all indexes reachable with 1 jump, then with 2, and so on. You do not need a queue. Track the end of the current layer (current_end) and the farthest point seen (farthest). When you reach the layer's end, you must take one more jump.

Python Jump game II: minimum jumps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Problem 3: Gas station

There are n stations on a circle. gas[i] is the fuel you can take at station i, and cost[i] is the fuel needed to drive from i to the next station. Starting with an empty tank, find a station index from which you can complete one full lap, or -1.

Brute force

Try every start and simulate the lap: O(n^2) time.

Greedy, in two observations

  1. If the total gas is less than the total cost, no start works.
  2. If you start at s and your tank first goes negative when you try to leave station j, then no station between s and j can be a valid start either. You reached each of them with a tank that was not negative, so starting fresh there gives you no more fuel than you had, and you still fail at j. So skip straight to j + 1.
Python Gas station in one pass

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Because the total is at least zero, the final candidate must work. Time O(n), space O(1).

Problem 4: Candy

Children stand in a line with ratings. Each child gets at least one candy, and a child with a higher rating than a neighbor must get more candy than that neighbor. Minimize the total.

A single pass cannot see both neighbors at once, so split the rule in two:

  • Left to right: if ratings[i] > ratings[i-1], then candy[i] = candy[i-1] + 1.
  • Right to left: if ratings[i] > ratings[i+1], then candy[i] = max(candy[i], candy[i+1] + 1).
TEXT
ratings:        1  0  2
left pass:      1  1  2
right pass:     2  1  2     (child 0 beats child 1, needs more than 1)
total = 5

Each pass fixes one direction of the rule, and the max in the second pass keeps what the first pass already guaranteed.

Python Candy distribution with two passes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(n) for the give list.

Problem 5: Task scheduler

Tasks are letters. The same letter must be separated by at least n other slots (a cooldown). Each slot runs one task or sits idle. What is the minimum number of slots?

The bottleneck is the most frequent letter. Say its count is m. It needs m - 1 full gaps of length n + 1 between its copies, plus a final row:

TEXT
tasks = A A A B B C, n = 2
A B C | A B _ | A        (m - 1) * (n + 1) + 1 = 7 slots, one idle

Other letters fill the gaps. If k letters are tied for the highest count, the last row holds k tasks, giving (m - 1) * (n + 1) + k. And if there are so many different tasks that no idle slot is needed, the answer is just the number of tasks. So:

TEXT
answer = max(len(tasks), (m - 1) * (n + 1) + k)
Python Task scheduler by formula

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n) to count, space O(1) for at most 26 letters.

Problem 6: Assign cookies

Each child g[i] wants a cookie of size at least g[i]. Each cookie s[j] can go to one child. Maximize the number of content children.

Greedy: sort both. Give each cookie, smallest first, to the least greedy child who is still waiting, if it is big enough. Walking through the cookies with one pointer on the children does it: if the cookie satisfies the current child, the child is content and the pointer advances; otherwise the cookie is too small for this child (and for every hungrier one), so discard it.

Why it works. The hungriest children can only be satisfied by large cookies, so do not waste them on small appetites. Matching smallest to smallest is the exchange-argument-safe move.

Python Assign cookies with two pointers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n log n + m log m) for sorting, space O(n + m) for the sorted copies.

Problem 7: Minimum product subset

Pick a non-empty subset of a list so that the product of its elements is as small as possible (as negative as possible). Sorting is not even needed; you only have to think about signs.

  • Multiply all negatives and all positives. Zeros are left out, because a zero would erase a negative product.
  • If the count of negatives is odd, that product is already negative. Done.
  • If the count is even, the product is positive, so drop the negative closest to zero (the largest one), which makes the product negative and as large in magnitude as possible.
  • If there are no negatives: a zero in the list gives 0; otherwise the answer is the smallest positive element.
  • A one-element list is the element itself.
Python Minimum product subset by signs

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n), space O(n) for the filtered lists.

Problem 8: Maximum sum after exactly K negations

You must flip the sign of an element exactly K times (the same element may be flipped repeatedly). Maximize the sum.

Flipping the smallest element is always the best single move: if it is negative you gain twice its size, and if everything is non-negative you lose the least. A min-heap hands you that element each round. Once the smallest is 0 or you reach a point where flips only alternate one value, the rest of the flips change nothing or lose a little, and the heap handles that naturally.

Python K negations with a min-heap

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O((n + K) log n).

Problem 9: Maximum sum of disjoint pairs with a small difference

Given numbers and a limit K, form disjoint pairs whose members differ by less than K, so that the total of all paired numbers is as large as possible. A number may stay unpaired.

Sort the list and look from the largest end. The biggest number is the most valuable one, so try to use it. If it can pair with its sorted neighbor (difference below K), pair them: the neighbor is the closest, so it is the most likely partner, and nothing else could pair with the largest while leaving a better set. Otherwise the largest number cannot pair with anything (every other number is even farther away), so skip it.

Python Pairing from the largest end

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O(n log n) for the sort. The pairing loop is O(n). More greedy exercises on scheduling, assignment and approximation follow in job sequencing and Egyptian fractions.

Problem 10: Minimum cost to cut a board

A board is split into unit squares by m - 1 vertical and n - 1 horizontal cutting lines. Each line has a cost. A cut along a line costs cost x (number of pieces the line currently crosses): a vertical cut made when the board is already in h horizontal strips must cut through all h pieces. What is the cheapest way to cut the board into 1x1 squares?

Expensive lines should be cut early, while the number of pieces they cross is still small. So take all cost values from both directions, sort them in descending order, and always cut the most expensive remaining line. Cutting a vertical line increases the count of vertical pieces (and so the multiplier for later horizontal cuts), and vice versa.

Python Cutting a board into squares

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time O((m + n) log (m + n)). As in the earlier problems, the sort carries the argument: swapping two adjacent cuts so the cheaper one goes first never lowers the total.

Common mistakes

  • Sorting by the wrong key. In fractional knapsack the key is the ratio, not the value or the weight alone.
  • Assuming greedy works because the first example does. Test on a small case where you can enumerate the best answer by hand.
  • Forgetting the feasibility check. Gas station needs the total-gas test; the loop alone can return a start that fails.
  • Off-by-one in ranges. Jump game II loops to len(nums) - 1, because standing on the last index needs no further jump.
  • Mutating inputs unexpectedly. list.sort() sorts in place; use sorted() if the caller still needs the original order.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why is ratio-greedy correct for fractional knapsack but not for 0/1 knapsack?

    The swap argument needs pieces that can be exchanged at their ratio. With whole items you can leave unused capacity, so a locally best ratio can block a better combination.
  2. 2. In the jump game, what single value is enough to decide if the end is reachable?

    Every index up to the farthest reach is reachable, so one running maximum summarizes all possible paths.
  3. 3. In the gas station problem, when your tank goes negative at station j starting from s, what do you do?

    Any station between s and j would arrive at j with no more fuel than you had, so it fails too. Only the total-gas check can prove that no start works at all.
  4. 4. Why does the candy problem use two passes?

    Each pass handles one direction of the neighbor constraint. Taking the max in the second pass preserves what the first pass established.
  5. 5. What drives the answer of the task scheduler problem?

    The most frequent task forces the layout of gaps; other tasks fit into them, and if there are enough tasks the total is just the task count.

Summary

  • Greedy problems come in two shapes: sort by a clever key, or keep one running quantity while scanning.
  • Fractional knapsack: sort by value per weight, cut the last item. O(n log n).
  • Jump game: track the farthest reach; the minimum-jumps variant counts BFS layers without a queue. O(n).
  • Gas station: if total gas covers total cost, restart the start index whenever the tank dips below zero. O(n).
  • Candy: one left-to-right pass and one right-to-left pass with max. O(n).
  • Task scheduler: the most frequent task decides the layout; the answer is max(len(tasks), (most - 1) * (n + 1) + tied).
  • Assign cookies: sort both lists and match each cookie to the smallest child it satisfies.
  • Minimum product subset: decide by the signs; drop the negative closest to zero if the count of negatives is even.
  • K negations: always flip the current minimum, with a min-heap.
  • Disjoint pairs with a small difference: sort and pair from the largest end when the neighbor is within K.
  • Always justify a greedy rule with a swap argument, and test it against a small brute force. Greedy vs dynamic programming shows what happens when it fails.

Next: Job Sequencing, Egyptian Fractions and Pairing Problems