Skip to content
Tutorials Center
My learning

Topics

Lesson 171 of 225 ยท Greedy Algorithms

Job Sequencing, Egyptian Fractions and Pairing Problems

Solve job sequencing with deadlines (heap and union-find), Egyptian fractions, policemen and thieves and mice to holes with greedy Python code.

Some greedy problems fit one of two moulds. In the first you are handed a set of tasks with deadlines and profits, and you must choose which to keep. In the second you pair up items from two groups, or break a number into pieces, and one clean rule tells you what to do next. This lesson covers four problems that look unrelated but all end with "sort, then take the obvious best".

The problems are job sequencing with deadlines, Egyptian fractions, policemen and thieves, and mice to holes. Each comes with a short argument for why the greedy rule is safe, and each is tested against a brute force, because a wrong greedy looks as convincing as a right one.

Job sequencing with deadlines

You have n jobs. Each takes exactly one unit of time, has a deadline (it must finish by that time slot) and a profit you earn only if it finishes in time. Only one job runs per slot. Which jobs should you run to earn the most?

TEXT
job  deadline  profit
a        4       20
b        1       10
c        1       40
d        1       30
e        3       15

Three jobs (b, c, d) all want slot 1, and only one can have it. The best choice there is c, worth 40. Slot 3 is free for e (deadline 3), and a (deadline 4) takes slot 4. Total: 40 + 15 + 20 = 75.

Greedy 1: a min-heap of chosen profits

Sort the jobs by deadline. Walk through them and push each profit onto a min-heap of "jobs I plan to run". A heap holding more jobs than the current deadline is infeasible, since at most deadline jobs fit into slots 1..deadline. When that happens, throw away the cheapest job in the heap.

Why is that safe? At every step the heap holds the best feasible set among the jobs seen so far. When a new job makes it too large, removing the smallest profit leaves the best set of the allowed size. This is the same exchange idea as in interval scheduling: never keep a worse job when a better one could take its place.

Python Job sequencing 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 is O(n log n): one sort plus n heap operations. This version tells you which jobs to run, but not their exact slots. Any feasible set can be ordered by deadline, so the slots follow.

Greedy 2: latest free slot with union-find

The classic version goes the other way. Sort by profit, highest first. Give each job the latest free slot not after its deadline. Taking the latest slot keeps the earlier ones open for jobs with tighter deadlines. If no free slot exists, skip the job.

Scanning for a free slot is O(n) per job, which makes the whole thing O(n^2). A union-find fixes that. Let find(t) return the latest free slot at or before t. When you fill slot t, link it to t - 1, so the next search skips it. Slot 0 means "none free".

Python Job sequencing with union-find

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 output shows slot 2 empty: nothing with deadline 2 exists, and the better jobs already used slots 1, 3 and 4. Time is O(n log n) for the sort plus nearly O(n) for the union-find. Both methods earn the same total on every input, which is a useful self-check when you write your own.

When two greedy methods for the same problem agree on random inputs, that is strong evidence both are right. Comparing against a tiny brute force (try every subset and order) on inputs of five or six jobs is even better.

Egyptian fractions

Ancient Egyptians wrote fractions as sums of distinct unit fractions (fractions with numerator 1): 6/14 = 1/3 + 1/11 + 1/231. Every positive fraction has such a decomposition, and a greedy rule finds one.

The rule: for num/den, take the largest unit fraction that does not exceed it. That is 1/ceil(den/num). Subtract it, and repeat on the remainder.

TEXT
6/14:  ceil(14/6)  = 3   take 1/3    remainder 6/14 - 1/3 = 4/42
4/42:  ceil(42/4)  = 11  take 1/11   remainder 4/42 - 1/11 = 2/462
2/462: ceil(462/2) = 231 take 1/231  remainder 0

Why does it end? The numerator of the remainder is always smaller than the numerator before, so after at most num steps it hits zero. The denominators may grow very fast, though, so the answer can contain huge numbers. Use integers, and use -(-den // num) to take a ceiling without going through floats, which would overflow or lose digits.

Python Egyptian fractions

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 greedy answer is valid but not always the shortest or the tidiest. 5/121 needs just five terms, yet the last denominator has 25 digits, and other decompositions may use smaller numbers. For "any valid decomposition" the greedy rule is enough; "the best one" needs search.

Policemen and thieves

A row of cells holds policemen P and thieves T. A policeman can catch one thief, and only one within distance k (to the left or right). What is the largest number of thieves that can be caught?

Keep two sorted lists of positions, one for each side, and walk them with two pointers.

  • If the current policeman and thief are within k of each other, match them and advance both.
  • Otherwise advance the pointer that is further left: that person is too far from everyone still to come, so they can never be matched.

This matches earliest with earliest, which leaves the most room for the later ones. The swap argument is the usual one: if an optimal answer matches them differently, exchanging partners never reduces the count.

Python Policemen and thieves 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 is O(n), because each pointer only moves forward. Space is O(n) for the position lists.

Mice to holes

There are n mice and n holes on a line, each hole fits one mouse. All mice move at the same speed. You want to assign mice to holes so that the last mouse to arrive arrives as early as possible. That means minimizing the maximum distance any mouse travels.

Sort both lists and pair them in order: the smallest mouse with the smallest hole, and so on. The answer is the largest gap between paired positions.

Why? Suppose two mice m1 < m2 go to holes h1 > h2 (crossed paths). Swapping to m1 -> h2 and m2 -> h1 never makes the worst distance larger. Uncrossing all pairs gives the sorted pairing.

Python Mice to holes

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 sorts.

Common mistakes

  • Using floats for Egyptian fractions. Floats lose digits quickly here; plain integers with an integer ceiling are exact and fast.
  • Picking the earliest free slot in job sequencing. Always take the latest free slot not after the deadline, so tight deadlines keep their options.
  • Forgetting that deadlines can exceed the number of jobs. Cap the deadline at the maximum deadline (or the job count) when sizing the union-find array.
  • Moving the wrong pointer in policemen and thieves. Advance the one that is further left; moving the other can skip a valid match.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. In the heap version of job sequencing, what do you remove when the heap holds more jobs than the current deadline?

    The heap must hold at most deadline jobs. Dropping the cheapest one keeps the most profitable feasible set.
  2. 2. In the union-find version, why does a job take the LATEST free slot before its deadline?

    A job with a late deadline can use many slots, so it should use the one that blocks the fewest other jobs.
  3. 3. What does the greedy rule for Egyptian fractions take at each step?

    That is 1/ceil(den/num). The new numerator is always smaller than the old one, so the process ends.
  4. 4. In policemen and thieves, which pointer moves when the current pair is farther apart than k?

    The one further left is too far from every remaining person on the other side, so it can never be matched.
  5. 5. Which pairing minimizes the longest trip in mice to holes?

    Crossed pairs can be uncrossed without increasing the maximum distance, which leaves the sorted pairing.

Summary

  • Job sequencing with deadlines: either sort by deadline and keep a min-heap of profits, or sort by profit and give each job the latest free slot with union-find. Both are O(n log n).
  • Egyptian fractions: repeatedly take 1/ceil(den/num); use integer arithmetic because denominators grow fast.
  • Policemen and thieves: sorted positions plus two pointers, advancing the one further left on a miss.
  • Mice to holes: sort both sides, pair in order, answer is the largest gap.
  • A small brute force is the cheapest way to catch a wrong greedy rule.

Next: Minimize Cash Flow, Water Connection and Cutting a Board