Unit 4: Sort, Sweep, Grab

In a contest, nobody writes a sort

You spent a whole unit of the Python track on bubble sort and merge sort, and that was worth doing — but here you call sort() and think about something else.

It costs about n log n, which for a million items is twenty million steps. Affordable. Two nested loops over the same million is not.

Python

import math

for n in [1000, 100000, 1000000]:
    print(n, n * math.floor(math.log2(n)), n * n)

It prints

1000 9000 1000000
100000 1600000 10000000000
1000000 19000000 1000000000000

Sorting by a part of each item

Contest data is usually pairs — a name and an age, a start and an end, a weight and a value. key says which part to sort on, and reverse=True turns it round.

sorted() gives a new list; .sort() changes the one you have.

Python

people = [("ann", 12), ("bob", 9), ("cal", 15)]

print(sorted(people, key=lambda p: p[1]))
print(sorted(people, key=lambda p: p[1], reverse=True))

It prints

[('bob', 9), ('ann', 12), ('cal', 15)]
[('cal', 15), ('ann', 12), ('bob', 9)]

Sorting puts the answer next to itself

"Which two of these numbers are closest together?" is a question about every pair — a million million of them for a million numbers.

Sort first and the two closest are neighbours, so one pass finds them. That is the whole trick, and it turns up again and again.

Python

numbers = sorted([9, 3, 7, 3, 12])
print(numbers)

gap = numbers[1] - numbers[0]
for i in range(1, len(numbers)):
    gap = min(gap, numbers[i] - numbers[i - 1])

print(gap)

It prints

[3, 3, 7, 9, 12]
0

Why the closest pair must be neighbours

Suppose the two closest numbers had something sitting between them once sorted. Then that middle number is closer to each of them than they are to each other — so they were not the closest pair after all.

A contradiction, so it cannot happen. That kind of one-line argument is what lets you skip work safely.

Find two numbers that add up to a target

Checking every pair is O(n * n). On a sorted list there is a one-pass way: a finger at each end.

Too small? The left finger has to move right — nothing smaller can help. Too big? The right finger moves left. They can only ever move towards each other, so it is O(n).

Python

numbers = [1, 4, 5, 6, 7, 9, 11]
target = 13

left = 0
right = len(numbers) - 1
while left < right:
    total = numbers[left] + numbers[right]
    if total == target:
        print(numbers[left], numbers[right])
        break
    if total < target:
        left += 1
    else:
        right -= 1

It prints

4 9

Why moving a finger cannot lose the answer

Say the total is too small. The left number is now paired with the biggest partner there is, and it still fell short — so that left number is in no pair that works, ever. Dropping it loses nothing.

That argument is the difference between a fast algorithm and a lucky one.

The same idea as a sliding window

Now: the longest run of neighbours whose total stays under a limit. Push the right edge along, and whenever the total goes over, drag the left edge up until it fits.

Each edge only ever moves right, so together they take 2n steps however wide the window gets.

Python

numbers = [2, 4, 1, 3, 5]
limit = 8

left = 0
total = 0
best = 0
for right in range(len(numbers)):
    total += numbers[right]
    while total > limit:
        total -= numbers[left]
        left += 1
    best = max(best, right - left + 1)

print(best)

It prints

3

A while inside a for is not always n times n

It looks like two nested loops, and it is not. The inner while can only run as many times in total as the left edge can move, and the left edge can move n times in its whole life.

So the whole thing is O(n). Counting total moves rather than moves per round is a habit worth building.

The greedy plan

Take whatever looks best right now, never change your mind, never look back.

It is the fastest kind of algorithm there is and it is wrong surprisingly often. The skill is telling the two apart before submitting.

Where greedy works: making change with real coins

Pay 63 pence with 1, 2, 5, 10, 20 and 50 pence pieces. Take the biggest coin that fits, again and again: 50, 10, 2, 1. Four coins, and no arrangement does better.

Real coin systems are built so that this is true.

Python

def greedy(coins, amount):
    used = 0
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used += 1
    return used

print(greedy([1, 2, 5, 10, 20, 50], 63))

It prints

4

Where greedy breaks: invented coins

Now the coins are 1, 4 and 5, and you owe 8. Greedy grabs the 5, then needs three 1s: four coins.

Two 4s would have done it. Greedy never considers that, because taking the 5 looked better at the time.

Python

def greedy(coins, amount):
    used = 0
    for c in sorted(coins, reverse=True):
        while amount >= c:
            amount -= c
            used += 1
    return used

def best(coins, amount):
    if amount == 0:
        return 0
    answer = 99
    for c in coins:
        if c <= amount:
            answer = min(answer, 1 + best(coins, amount - c))
    return answer

print(greedy([1, 4, 5], 8), best([1, 4, 5], 8))

It prints

4 2

So how do you know?

You prove it, with an exchange argument: take any best-possible answer, and show you can swap its first choice for the greedy choice without making it worse. If you can, greedy is safe.

If you cannot find that argument in a minute or two, assume greedy is wrong and reach for the search or the DP instead. The next lesson has an argument that works.

One hall, many bookings

Each event has a start and an end. Two events cannot overlap in the hall. Fit in as many as you can — their lengths do not matter, only the count.

There are three obvious greedy plans. Two of them are wrong.

Wrong plan one: earliest start

Take whatever begins soonest. One long booking at the start eats the whole day.

Python

events = [(1, 10), (2, 3), (4, 5)]

chosen = []
finished = 0
for start, end in sorted(events):
    if start >= finished:
        chosen.append((start, end))
        finished = end

print(chosen)

It prints

[(1, 10)]

Wrong plan two: shortest event

Take the shortest one first. Here the short middle booking blocks two long ones that would have fitted perfectly either side of it.

Python

events = [(0, 10), (9, 11), (10, 20)]

chosen = []
for start, end in sorted(events, key=lambda e: e[1] - e[0]):
    if all(end <= s or start >= f for s, f in chosen):
        chosen.append((start, end))

print(sorted(chosen))

It prints

[(9, 11)]

Right plan: earliest finish

Take the event that ends soonest, then the next one that starts after it, and so on.

It beats both wrong plans on their own data — and unlike them, it can be proved.

Python

def most_events(events):
    count = 0
    finished = 0
    for start, end in sorted(events, key=lambda e: e[1]):
        if start >= finished:
            count += 1
            finished = end
    return count

print(most_events([(1, 10), (2, 3), (4, 5)]))
print(most_events([(0, 10), (9, 11), (10, 20)]))
print(most_events([(1, 3), (2, 5), (3, 9), (6, 8)]))

It prints

2
2
2

The proof, in two sentences

Take any best possible timetable and look at its first event. Swapping it for the one that finishes soonest cannot clash with anything later, because it frees the hall earlier — so the swapped timetable is just as big.

Repeat down the list and you have turned any best answer into the greedy one. So greedy is a best answer too.