Module assignment: Greedy toolkit in Python

Why this assignment

Reading about greedy algorithms is not the same as writing one that passes a judge. A judge is a program that runs your code on test inputs and compares the output with the correct answer. This assignment asks you to put the four lessons into one program. You will sort meetings by end time, fill a bag by value per unit of weight, schedule jobs in the latest free hour, and merge frequencies with a min-heap. Each section reuses an idea from one lesson, so you cannot finish it without remembering the rule, the reason it is safe and the Python detail that makes it work.

The assignment is also a test of habit. Greedy programs fail quietly. A wrong sort key or a float where an integer belongs does not crash. It prints a plausible number that is slightly too small, or a number with a decimal point. Part of the work is writing the small tests that catch those mistakes, before you submit.

Time yourself honestly. Most people who finish this well spend about 40 minutes on the code and another 15 minutes on the tests and the explanation comments.

The program you write

Your program reads one input made of four sections, in a fixed order. Each section starts with a header line that holds its count, so the program always knows where the next section begins. Then it prints exactly four lines, one per section, with the labels shown.

The program reads the whole input at once and splits it into tokens. A token is one piece of text between spaces or line breaks, here one number. Line breaks do not matter to the program. Only the order of the numbers matters.

Section A is the meetings problem from lesson 1. The first line holds n. Each of the next n lines holds a start and an end. Print meetings: followed by the largest number of meetings that do not overlap. A meeting may start at the exact moment another ends.

Section B is the fractional knapsack from lesson 2. The first line holds n and the capacity C. Each of the next n lines holds a value and a weight. Fill the bag by value per unit of weight, cut the last item if needed, and print knapsack: followed by the largest whole number that is not more than the best total value. The largest whole number that is not more than a value is called its floor. Print the floor, not a decimal.

Section C is the job sequencing problem from lesson 2. The first line holds n. Each of the next n lines holds a deadline and a profit. Choose the jobs with the most profit, each in a free hour on or before its deadline, and print jobs: followed by the total profit.

Section D is the Huffman cost from lesson 3. The first line holds n. The next line holds n frequencies. Merge the two smallest values again and again, add each merged value to the total, and print huffman bits: followed by the total. If there is only one frequency, the total is 0.

Here is a complete sample input. It uses examples from the lessons, so you can check your reasoning against the worked examples.

11
1 4
3 5
0 6
5 7
3 9
5 9
6 10
8 11
8 12
2 14
12 16
3 50
60 10
100 20
120 30
5
2 100
1 19
2 27
1 25
3 15
6
5 9 12 13 16 45

The expected output is these four lines.

meetings: 4
knapsack: 240
jobs: 142
huffman bits: 224

Requirements checklist

Work through this list before you submit. Each item is something the grader checks, by reading your code or by running it on hidden inputs.

Starter code

Start from this skeleton. It reads nothing yet and does not compute anything. Fill in each function, then the program is already wired to call them in the order of the sections. Each function takes the same tokens iterator, so each one reads its own section. An iterator is an object that hands out one item at a time and remembers where it stopped. Each call to next(tokens) gives the next token.

import heapq
import sys
from fractions import Fraction
 
 
def meetings(tokens):
    # Section A: most non-overlapping meetings. Greedy rule: earliest end first.
    # your code here
    return 0
 
 
def knapsack(tokens):
    # Section B: fractional knapsack. Greedy rule: highest value per unit of weight first.
    # your code here
    return 0
 
 
def jobs(tokens):
    # Section C: job sequencing. Greedy rule: highest profit first, latest free hour.
    # your code here
    return 0
 
 
def huffman(tokens):
    # Section D: Huffman cost. Greedy rule: merge the two smallest weights.
    # your code here
    return 0
 
 
def main():
    tokens = iter(sys.stdin.read().split())
    print(f"meetings: {meetings(tokens)}")
    print(f"knapsack: {knapsack(tokens)}")
    print(f"jobs: {jobs(tokens)}")
    print(f"huffman bits: {huffman(tokens)}")
 
 
if __name__ == "__main__":
    main()

The last two lines run main only when you start the file directly, for example with python3 assignment.py. If another program imports the file, main does not run. This is the usual pattern in Python files.

Build the program one section at a time. Test each section before you start the next. The stages below show the code for each step.

Step by step, with stages

Try each stage on your own first. If you are stuck for more than twenty minutes, read the stage for that step. Each stage shows code that does the work up to that point, so you can compare it with your own code.

Stage 1: section A on its own

Read n, then the n pairs, into a list of tuples. A tuple is a fixed group of values written in parentheses, such as (2, 8). Sort the list by the end, which is the second value in each tuple. Walk through the sorted list with a last_end variable. It starts as None, which means no meeting has been taken yet. Take a meeting when its start is at least last_end.

import sys
 
 
def meetings(tokens):
    n = int(next(tokens))
    rows = []
    for _ in range(n):
        start = int(next(tokens))
        end = int(next(tokens))
        rows.append((start, end))
    rows.sort(key=lambda row: row[1])
    last_end = None
    count = 0
    for start, end in rows:
        if last_end is None or start >= last_end:
            count += 1
            last_end = end
    return count
 
 
def main():
    tokens = iter(sys.stdin.read().split())
    print(f"meetings: {meetings(tokens)}")
 
 
if __name__ == "__main__":
    main()

Save the code as assignment.py. Run python3 assignment.py, then type the first twelve lines of the sample. Press Ctrl+D on its own line to send the end of the input. On Windows, press Ctrl+Z and then Enter. The output should be meetings: 4.

Stage 2: section B added

Python can compare fractions exactly with Fraction. Fraction(60, 10) is exactly 6, and Fraction(100, 20) is exactly 5. A float is a number stored with limited precision, so two ratios that are equal in theory can come out slightly different. A Fraction does not round, so the sort order is exact.

The sort key returns the fraction for each item. reverse=True puts the highest value per unit of weight first. Fill the bag in that order. For the item that does not fit, take its share with value * capacity // weight. The // operator divides and keeps only the whole part, which is the floor for positive numbers.

Replace the knapsack function with this one, add from fractions import Fraction at the top, and print knapsack in main.

def knapsack(tokens):
    n = int(next(tokens))
    capacity = int(next(tokens))
    items = []
    for _ in range(n):
        value = int(next(tokens))
        weight = int(next(tokens))
        items.append((value, weight))
    items.sort(key=lambda item: Fraction(item[0], item[1]), reverse=True)
    total = 0
    for value, weight in items:
        if capacity == 0:
            break
        if weight <= capacity:
            total += value
            capacity -= weight
        else:
            total += value * capacity // weight
            capacity = 0
    return total

Input to type: the first sixteen lines of the sample. The output should be meetings: 4 and knapsack: 240.

Stage 3: section C added

Sort the jobs by profit, highest first. Keep a list called parent, where parent[h] points to the latest hour at or before h that might still be free. Cap each deadline at n before you search, so the list stays small. When a job takes hour h, set parent[h] = h - 1. Hour 0 means no hour is left, and it points to itself.

Python lists start at index 0, so parent has n + 1 entries, for hours 0 through n. The helper find follows the links until it reaches an hour that points to itself. It also shortens the links it passes, so later searches are faster.

Replace the jobs function with this one, and keep the find helper inside it.

def jobs(tokens):
    n = int(next(tokens))
    rows = []
    for _ in range(n):
        deadline = int(next(tokens))
        profit = int(next(tokens))
        rows.append((deadline, profit))
    rows.sort(key=lambda row: row[1], reverse=True)
    parent = list(range(n + 1))
 
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
 
    total = 0
    for deadline, profit in rows:
        slot = find(min(deadline, n))
        if slot > 0:
            total += profit
            parent[slot] = slot - 1
    return total

Input to type: the first twenty-two lines of the sample. The output should be meetings: 4, knapsack: 240 and jobs: 142.

Stage 4: section D, and the complete reference

Section D needs a min-heap, which is a structure that always gives back the smallest value first. Python has one in the heapq module. heapq.heapify arranges a list into heap order. heapq.heappop removes and returns the smallest value. heapq.heappush adds a value.

Each step pops the two smallest values, adds them, adds the sum to the total, and pushes the sum back. Python integers have no size limit, so the total cannot wrap around. A Java long is not needed here.

Replace the huffman function with this one.

def huffman(tokens):
    n = int(next(tokens))
    heap = [int(next(tokens)) for _ in range(n)]
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        merged = heapq.heappop(heap) + heapq.heappop(heap)
        total += merged
        heapq.heappush(heap, merged)
    return total

The complete program is below. It is a reference solution, so compare it with your own work after you have tried it yourself. Each function has its greedy rule in a comment, and the rule's reason is the explanation you write for the 100% level.

import heapq
import sys
from fractions import Fraction
 
 
def meetings(tokens):
    # Section A. Greedy rule: earliest end first.
    # It is safe because the meeting that ends first can replace any other first meeting
    # in a best schedule without causing a clash.
    n = int(next(tokens))
    rows = []
    for _ in range(n):
        start = int(next(tokens))
        end = int(next(tokens))
        rows.append((start, end))
    rows.sort(key=lambda row: row[1])
    last_end = None
    count = 0
    for start, end in rows:
        if last_end is None or start >= last_end:
            count += 1
            last_end = end
    return count
 
 
def knapsack(tokens):
    # Section B. Greedy rule: highest value per unit of weight first, cut the last item.
    # It is safe because each unit of capacity goes to the best value per weight still left,
    # and a cut item can be split, so the bag gets the best mix of the items.
    n = int(next(tokens))
    capacity = int(next(tokens))
    items = []
    for _ in range(n):
        value = int(next(tokens))
        weight = int(next(tokens))
        items.append((value, weight))
    items.sort(key=lambda item: Fraction(item[0], item[1]), reverse=True)
    total = 0
    for value, weight in items:
        if capacity == 0:
            break
        if weight <= capacity:
            total += value
            capacity -= weight
        else:
            total += value * capacity // weight
            capacity = 0
    return total
 
 
def jobs(tokens):
    # Section C. Greedy rule: highest profit first, each job in the latest free hour
    # on or before its deadline.
    # It is safe because a job that fits is added without moving any job already chosen,
    # and the latest free hour keeps early hours open for jobs with tight deadlines.
    n = int(next(tokens))
    rows = []
    for _ in range(n):
        deadline = int(next(tokens))
        profit = int(next(tokens))
        rows.append((deadline, profit))
    rows.sort(key=lambda row: row[1], reverse=True)
    parent = list(range(n + 1))
 
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
 
    total = 0
    for deadline, profit in rows:
        slot = find(min(deadline, n))
        if slot > 0:
            total += profit
            parent[slot] = slot - 1
    return total
 
 
def huffman(tokens):
    # Section D. Greedy rule: merge the two smallest weights.
    # Each merge adds its weight to the total, and that total is the number of bits
    # the message needs.
    n = int(next(tokens))
    heap = [int(next(tokens)) for _ in range(n)]
    heapq.heapify(heap)
    total = 0
    while len(heap) > 1:
        merged = heapq.heappop(heap) + heapq.heappop(heap)
        total += merged
        heapq.heappush(heap, merged)
    return total
 
 
def main():
    tokens = iter(sys.stdin.read().split())
    print(f"meetings: {meetings(tokens)}")
    print(f"knapsack: {knapsack(tokens)}")
    print(f"jobs: {jobs(tokens)}")
    print(f"huffman bits: {huffman(tokens)}")
 
 
if __name__ == "__main__":
    main()

Input to type: the full sample. The output should be the four lines shown above.

Test your program with these inputs

Before you submit, check your program on these two inputs. Each one tests a different edge case. The expected outputs were checked by hand against the rules and by the reference program above, so a mismatch means a bug in your program.

Test 1: back-to-back meetings, zero capacity, one job with a large deadline, one frequency. This input checks the >= rule, the capacity-zero stop, the deadline cap, and the single-frequency case.

Expected output:

meetings: 3
knapsack: 0
jobs: 7
huffman bits: 0

Test 2: two jobs with deadlines far above n, one item that fits whole, two frequencies. This input checks the deadline cap when two jobs compete for the same hours.

Expected output:

meetings: 2
knapsack: 10
jobs: 14
huffman bits: 7

If your program passes the sample and both tests, you have covered the main rules. The rubric below describes what the grade depends on.

Grading rubric

Your score depends on what the program does on the sample and on hidden inputs of the same kinds. The three levels describe what a program at each level looks like.

Level	What the program does
60%	Prints the four lines correctly on the sample. Each section uses the right sort key: end time for meetings, value per weight for the knapsack, profit for jobs, and the two smallest for Huffman. Some edge cases fail, such as back-to-back meetings, capacity zero or a single frequency.
80%	Passes the sample and the edge tests above. Uses integers, `Fraction` or `//` for every sum and ratio, so no float appears in the output. Caps deadlines at `n`, so the job list does not grow with a huge deadline. Prints exactly four lines with the labels, and nothing else.
100%	Everything at 80%, plus: each section has a comment that names the rule and gives the reason it is safe. The job section uses the `parent` list, not a scan back through all hours for each job. The program handles `n` of 0 in each section without an exception. Test inputs that you wrote yourself are included in your explanation, with the reason each one matters.

Two notes on the rubric. First, the difference between 60% and 80% is almost always one edge case. Find the edge cases before you submit. Second, the 100% level asks for an explanation, not only code. A short comment for each section is enough, but it must name the rule and say why it is safe, using ideas from lesson 4.

Common ways to lose points

Most lost points come from a short list of habits. Check each one before you submit.

The first is printing extra text. A debugging line such as print(heap) left in the code adds a fifth line to the output, and the judge rejects the whole run. Remove every debugging print, or send it to standard error with print(heap, file=sys.stderr). Standard error is a second output stream, and the judge does not compare it.

The second is reading the sections in the wrong order, or reading one token too many. Each section starts with its own count, so one extra next(tokens) call moves every later section by one value. A value that is not a number fails at once:

ValueError: invalid literal for int() with base 10: 'ten'

A value that is missing fails at the end of the input. The last line of the traceback is:

StopIteration

It means the program asked for more tokens than the input has. Test with the sample, because the sample makes that mistake visible at once.

The third is a float where an integer belongs. Python's / always gives a float. In the knapsack, using / for the cut item prints a decimal:

knapsack: 240.0

Large numbers make it worse. Compare these two lines:

print(10**17 * 3 / 7)
print(10**17 * 3 // 7)

Output:

4.2857142857142856e+16
42857142857142857

The float loses the last digits. The // operator keeps every digit of the whole part. Use // for every division that must give a whole number.

The fourth is sorting by the wrong key. Section A sorted by start gives the wrong answer on a small input. Input 3, then 0 10, 2 3 and 4 5:

rows.sort(key=lambda r: r[0])

With the start as the key, the program prints 1. The correct answer is 2, because the meetings 2 3 and 4 5 both fit and the long meeting 0 10 does not. Sort by the end, as the stage 1 code does, and the program prints 2.

Explain your choices

Write a short explanation of your program, in five to eight sentences, and keep it with the code. Say which sort key each section uses and why that key is the right one. Name one input where the wrong key gives a different answer. For the knapsack, say why whole items would not allow the same rule. For the jobs, say why the latest free hour is used. For Huffman, say what the total means in bits.

This explanation is what an interviewer asks for. Writing it now makes the interview answer shorter and clearer.

Summary of this module

Activity selection sorts by end time and takes each meeting that starts at or after the last end.
Fractional knapsack sorts by value per unit of weight, and job sequencing sorts by profit and uses the latest free hour.
Huffman coding merges the two smallest weights with a min-heap, and its cost is the sum of the merges.
The exchange argument proves a greedy choice is safe, and brute force tests find counterexamples.
Greedy fails for unusual coin sets, for whole-item knapsacks and for shortest paths with negative edges.