Skip to content
Tutorials Center
My learning

Topics

Lesson 172 of 225 ยท Greedy Algorithms

Minimize Cash Flow, Water Connection and Cutting a Board

Greedy Python solutions for settling group debts with two heaps, finding pipe chains in the water connection problem, and cutting a board at minimum cost.

Three small problems, three different greedy ideas. Minimize cash flow shows how reducing a tangle of debts to net balances makes a simple rule possible, and also where that rule stops being optimal. Water connection is a graph problem that turns into a plain walk once you notice each house has at most one pipe in and one out. Cutting a board asks you to pay as little as possible to cut a sheet into unit squares, and the answer is "do the expensive cuts first".

You should know heaps and the greedy idea. Nothing else is needed.

Minimize cash flow

Friends have lent each other money. Ana paid Bo 1000, Bo paid Cy 5000, and so on. Who should pay whom so that everyone ends up even, using as few payments as possible?

The first step removes most of the confusion: only each person's net balance matters. Add up what each person received and subtract what they paid. Someone with a positive balance is owed money (a creditor), someone with a negative balance owes money (a debtor), and the balances sum to zero.

TEXT
Ana -> Bo 1000     Bo -> Cy 5000     Cy -> Ana 2000
Cy -> Di 3000      Di -> Bo 500

net:  Ana +1000    Bo -3500    Cy 0    Di +2500

Cy is already square, and the original five payments collapse. Now apply a greedy rule: take the largest creditor and the largest debtor, let the debtor pay the smaller of the two amounts, and put whoever still has a balance back. Each payment settles at least one person completely, so there are at most n - 1 payments.

Python Settling group debts with two heaps

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.

The loop runs at most n - 1 times with O(log n) heap work each, so the time is O(n log n) after the O(d) pass over d debts.

This greedy is not always minimal. Finding the fewest possible payments is NP-hard: it asks you to split the people into as many groups as possible where each group's balances sum to zero. Take balances +9, +8, -8, -7, -2. Matching +8 with -8 and then settling +9 against -7 and -2 needs 3 payments, but the largest-with-largest rule makes 4. The greedy rule still gives a correct settlement with at most n - 1 payments; it just may not be the shortest.

The next TryIt proves the warning with a brute-force search for the true minimum.

Python Greedy versus the true minimum

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.

Water connection

A town has n houses numbered 1..n and p pipes. Pipe (a, b, d) runs from house a to house b and has diameter d. Each house has at most one outgoing and at most one incoming pipe. A house with an outgoing pipe but no incoming pipe needs a water tank on top of it, and a house with an incoming pipe but no outgoing pipe gets a tap. Report every tank/tap pair with the smallest diameter along its chain, because the thinnest pipe limits the flow.

Because every house has at most one pipe in and one out, the pipes form chains (and possibly cycles, which have no tank and are ignored). There is nothing to optimize in choosing: find each chain's start and walk it, tracking the minimum. That is greedy in the sense that the only decision is forced, and it is a good example of a graph problem that needs no graph algorithm.

TEXT
pipes: 7->4 (98)   4->6 (10)   5->9 (72)   9->7 (17)   2->8 (22)   3->1 (42)

chain 5 -> 9 -> 7 -> 4 -> 6:   min diameter = 10
chain 2 -> 8:                  min diameter = 22
chain 3 -> 1:                  min diameter = 42
Python Water connection: tanks, taps and thinnest pipes

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.

Each pipe is visited once, so the time is O(n + p) after sorting the starts (O(n log n), or O(n) if you loop 1..n instead). The cycle case prints an empty list: with no tank, no water enters it.

Cutting a board

A board is m by n units. Every cut line along a grid line has a cost: h[i] for the m - 1 horizontal cuts and v[j] for the n - 1 vertical cuts. You must cut it into m * n unit squares. Cutting a piece costs the cost of that line, and the same line must be cut once in every piece it crosses. So a horizontal cut made when the board already has V vertical pieces costs h[i] * V.

That is the key: early cuts are cheap in multiplier because there are few pieces, and later cuts get multiplied by the number of pieces already created in the other direction. So make the most expensive cuts first, while the multiplier is small.

Process all costs from largest to smallest. Keep h_pieces and v_pieces (both start at 1). A horizontal cut costs cost * v_pieces and increases h_pieces; a vertical cut costs cost * h_pieces and increases v_pieces.

TEXT
horizontal costs [3, 1, 2]   vertical costs [4, 2]

sorted: 4v 3h 2v 2h 1h   (ties: either order gives the same total)
start    h_pieces=1  v_pieces=1
4v : cost 4*1 = 4    v_pieces = 2
3h : cost 3*2 = 6    h_pieces = 2
2v : cost 2*2 = 4    v_pieces = 3
2h : cost 2*3 = 6    h_pieces = 3
1h : cost 1*3 = 3    h_pieces = 4
total = 23

Why it works. Swap any two adjacent cuts where the cheaper comes first. The expensive cut loses nothing in its own multiplier, and the cheap one gets a bigger multiplier, but the two effects together never cost more than the original order. Repeating swaps sorts the cuts in descending order.

Python Cutting a board at minimum cost

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((m + n) log(m + n)) for the sort.

Common mistakes

  • Treating individual debts as the problem. Always reduce to net balances first; the number of original debts does not matter.
  • Claiming the two-heap method is optimal. It is correct and gives at most n - 1 payments, but the minimum number of payments is NP-hard.
  • Walking a cycle forever. In water connection, start only from houses with no incoming pipe; a walk that begins on a cycle never ends.
  • Cutting cheap lines first. Every line cut multiplies by the pieces in the other direction, so expensive cuts belong at the start.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why do you compute net balances before settling debts?

    Any set of payments that gives each person the right net change is a valid settlement, so the original tangle collapses to one number per person.
  2. 2. What is true about the largest-creditor with largest-debtor greedy?

    Every payment settles at least one person, which bounds the count by n - 1. The true minimum is an NP-hard grouping problem.
  3. 3. In water connection, where does a walk start?

    That house is the tank end of a chain. Houses with incoming pipes are in the middle or at the end.
  4. 4. Why does a cycle of pipes produce no tank-tap pair?

    Tanks are houses with no incoming pipe. A cycle has none, so water never enters it.
  5. 5. In the board-cutting problem, why cut the most expensive lines first?

    A cut's price is its cost times the number of pieces in the other direction. Large costs should meet small multipliers.

Summary

  • Settling debts: compute net balances, then repeatedly pay the largest debtor to the largest creditor with two heaps. At most n - 1 payments, O(n log n), but not guaranteed minimal.
  • The true minimum number of payments is an NP-hard grouping problem; the greedy is a good, fast approximation.
  • Water connection: each house has at most one pipe in and out, so walk each chain from its tank and keep the minimum diameter. Cycles are ignored.
  • Board cutting: sort all cut costs in descending order, and charge each cut cost * pieces in the other direction.
  • Reduce a messy input to a simpler form (balances, chains, sorted costs) before looking for the greedy rule.

Next: Greedy Approximation: Set Cover, Bin Packing, k-Center and More