Sorting with keys and greedy

When you need to solve an optimization problem, sorting often comes first. A greedy algorithmgreedy algorithmAn algorithm that solves a problem by making locally optimal choices at each step without reconsidering earlier decisions.In the glossary makes the locally best choice at each step without revising earlier decisions. Sorting with the right criterion puts the best choices in front, so a greedy selection gives the globally optimal answer.

Sorting by attributes

The sorted() function takes a key parameter that determines the sort order. The key is a function that extracts a comparison value from each item.

Suppose you are scheduling tasks. Each task has a name and a duration in minutes.

tasks = [("write", 20), ("debug", 50), ("test", 15)]

To schedule by duration, sort using the second element of each tuple:

tasks = [("write", 20), ("debug", 50), ("test", 15)]by_duration = sorted(tasks, key=lambda t: t[1])print(by_duration)

The output is:

[('test', 15), ('write', 20), ('debug', 50)]

The lambda function extracts t[1], the duration, so sorted() orders the tasks from shortest to longest. You can also sort in reverse order by adding reverse=True.

Greedy choices with sorting

Many contest problems reward a greedy strategy after sorting. The idea is simple: sort by the criterion that matters, then make the obvious choice.

A worked example: you are loading boxes onto a truck. Each box has a weight and a value, and you take a whole box or leave it. The truck has a capacity, and you want to maximize the total value without exceeding it. One greedy heuristic sorts by value per unit weight and packs boxes in that order, taking each one that still fits.

1boxes = [2    ("A", 10, 50),   # weight=10, value=503    ("B", 5, 20),    # weight=5, value=204    ("C", 15, 80)    # weight=15, value=805]6capacity = 257
8# Sort by value per weight, descending9sorted_boxes = sorted(boxes, key=lambda b: b[2] / b[1], reverse=True)10
11total_weight = 012total_value = 013for name, weight, value in sorted_boxes:14    if total_weight + weight <= capacity:15        total_weight += weight16        total_value += value17        print(f"Pack {name}")18
19print(f"Total value: {total_value}")

The output is:

Pack CPack ATotal value: 130

Box C has the best value-to-weight ratio (80/15, about 5.3), so it goes first. Box A comes next (50/10, exactly 5). Box B would fit by weight, but the capacity is already used up by A and C.

This ratio heuristic does not always find the best possible total when boxes cannot be split. It happens to match the best total here, but a later section returns to why this matters.

Handling ties

When two items have the same sort key, Python preserves their original order (stable sort). Sometimes you want to break ties a different way.

Consider a race where runners have the same finishing time. You might break the tie by earlier bib number.

1runners = [2    ("Alice", 12.5, 101),3    ("Bob", 12.5, 99),4    ("Carol", 12.0, 100)5]6
7# Sort by time, then by bib number8sorted_runners = sorted(runners, key=lambda r: (r[1], r[2]))9for name, time, bib in sorted_runners:10    print(name, time, bib)

The output is:

Carol 12.0 100Bob 12.5 99Alice 12.5 101

The key is a tuple (r[1], r[2]). Python sorts by the first element, and uses the second to break ties. This avoids multiple sort calls or complex comparisons.

Common sorting mistakes

One frequent error is forgetting to handle the data type correctly. If you sort strings that look like numbers without converting them, the order will be lexicographic, not numeric. The string "100" comes before "20".

times_str = ["100", "20", "5"]print(sorted(times_str))  # Wrong: lexicographic orderprint(sorted(times_str, key=int))  # Correct: numeric order

The output is:

['100', '20', '5'][5, 20, 100]

Another mistake is using the wrong sort direction. If you want to pack the most valuable items first, sort in descending order by value. Forgetting reverse=True will pack low-value items first.

A second example: task scheduling

Suppose you have a list of tasks, each with a deadline and a processing time. You want to complete as many tasks as possible before their deadlines. A greedy approach is to sort by deadline (earliest first) and do tasks in that order.

1tasks = [2    ("A", 5, 2),3    ("B", 3, 1),4    ("C", 4, 2)5]6
7# Sort by deadline8tasks.sort(key=lambda t: t[1])9
10current_time = 011completed = []12for name, deadline, time in tasks:13    current_time += time14    if current_time <= deadline:15        completed.append(name)16    else:17        print(f"Task {name} missed deadline")18
19print(f"Completed: {completed}")

Sorting by deadline is the greedy choice, and it processes the most urgent task first at every step. It does not always maximize how many tasks finish on time. A schedule that does the short tasks first, even if their deadlines are later, can sometimes squeeze in more completions overall. Earliest-deadline-first is the right choice when the goal is to keep each task's own lateness small. It is the wrong tool when the goal is to maximize the count of tasks that finish on time.

The key difference between this example and the box-packing example is the criterion: one sorts by ratio, the other by absolute value. The pattern is the same: identify what matters (deadline, ratio, cost), sort by it, and greedily proceed.

Why sorting enables greedy

Sorting is often the first step in a greedy solution because it rearranges the data into an order where the greedy choice becomes obvious. Without sorting, you would have to search for the best choice at each step, which is slow. With sorting, the best choice is already in front of you.

This preprocessing cost pays off quickly when you have many choices to make. For a single selection, looping through unsorted data might be faster. For repeated selections or a large data set, sort first.

When greedy works

Greedy algorithms are tempting but not always correct. A greedy choice may look good now and prevent a better solution later. The best defense is to reason about the problem.

A greedy algorithm is optimal when the problem has the greedy choice propertygreedy choice propertyA property of optimization problems where a globally optimal solution always includes a locally optimal (greedy) choice made at the first step.In the glossary: a globally optimal solution always includes a greedy choice made at the first step. Sorting problems like task scheduling and fractional knapsack, where you may take part of an item, have this property. Others do not.

The box-packing example earlier is one where sorting by ratio is only a heuristic. A box must be taken whole or not at all. Because of that, some inputs leave capacity unused under the ratio order that a different combination would have filled with more total value. Fractional knapsack allows you to take, say, two-thirds of a box, so the ratio order is always correct there. The moment items become all-or-nothing, ratio order stops being a proof and becomes a good guess.

Test your intuition on any new problem. Ask yourself: is there an input where a different order would give a better result? If you cannot construct one, and you can argue why every counter-order fails, the greedy approach is likely correct. If the problem does not have optimal substructure, where the best solution to the whole problem is built from best solutions to smaller pieces, greedy fails.

Many competitive programming problems are solvable by sorting and one pass. Learn to recognize them. The key insight is that sorting rearranges the data so that a single greedy pass through the sorted sequence yields an optimal result. This is much cheaper than trying all permutations or using dynamic programming.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8
9    n = int(input_data[0])10    capacity = int(input_data[1])11
12    boxes = []13    idx = 214    for _ in range(n):15        weight = int(input_data[idx])16        value = int(input_data[idx + 1])17        boxes.append((weight, value))18        idx += 219
20    # Sort by value per weight, descending21    boxes.sort(key=lambda b: b[1] / b[0], reverse=True)22
23    total_weight = 024    total_value = 025    for weight, value in boxes:26        if total_weight + weight <= capacity:27            total_weight += weight28            total_value += value29
30    sys.stdout.write(str(total_value) + "\n")31
32
33if __name__ == "__main__":34    main()

3 25
10 50
5 20
15 80

130

The program reads the box data, sorts by value-to-weight ratio in descending order, and greedily packs boxes while capacity allows. This gives the best possible total for this particular set of boxes. As the earlier section explains, the same strategy is not guaranteed to be optimal on every input where boxes cannot be split.