Minimise the maximum: split into k groups

Minimising the maximum means splitting work so that whoever gets the most has as little as possible. When the work is an ordered list, such as the chapters of a book that must stay in order, and each of k people takes one unbroken run, the best split need not be found by trying splits. Guess a limit S and ask whether k people can cover the list without anyone going over S: one pass that fills each person in turn answers that, and a larger S never makes the answer worse. So the smallest workable S can be binary searched between the longest item and the total. Below are an original version of the problem, a measurement of how fast trying every split blows up, and the observation that makes the search possible.

The problem: sharing a textbook’s chapters

1. pages = [40, 25, 60, 15, 30, 20] and k = 3 give 65: the runs 40 + 25, 60 and 15 + 30 + 20.
2. The same chapters with k = 1 give 190, every page.
3. pages = [10, 20] and k = 3 give −1: three students cannot each take one of two chapters.

The brute force: try every split

Cutting n chapters into k runs means choosing k − 1 of the n − 1 gaps between chapters, so there are C(n − 1, k − 1) splits. Try them all and keep the best: a perfect judge for small inputs, and hopeless beyond them.

"""The smallest possible largest share, by trying every way to cut the chapters into k runs: the brute force."""
import math
import time
from itertools import accumulate, combinations


def smallest_largest_by_trying(pages, k):
    n = len(pages)
    if k > n:
        return -1, 0
    upto = [0, *accumulate(pages)]  # upto[i] = pages of chapters 0 .. i - 1
    best, splits = None, 0
    for cuts in combinations(range(1, n), k - 1):  # where students 2 .. k start
        bounds = (0, *cuts, n)
        largest = max(upto[b] - upto[a] for a, b in zip(bounds, bounds[1:]))
        best = largest if best is None else min(best, largest)
        splits += 1
    return best, splits


for pages, k in [([40, 25, 60, 15, 30, 20], 3), ([40, 25, 60, 15, 30, 20], 1), ([10, 20], 3), ([40, 25, 60, 15, 30, 20], 6)]:
    best, splits = smallest_largest_by_trying(pages, k)
    print(f"k = {k}: {best} after {splits:,} split{'' if splits == 1 else 's'}")

big = [((7 * i) % 23) + 5 for i in range(28)]  # 28 chapters of 5 to 27 pages
start = time.perf_counter()
best, splits = smallest_largest_by_trying(big, 8)
per_split = (time.perf_counter() - start) / splits
print(f"28 chapters, 8 students: {splits:,} splits, about {per_split * 1e6:.1f} microseconds each")


def duration(seconds):
    for unit, size in (("year", 365 * 86_400), ("day", 86_400), ("hour", 3_600), ("minute", 60), ("second", 1)):
        if seconds >= size or unit == "second":
            value = round(seconds / size)
            return f"about {value:,} {unit}{'' if value == 1 else 's'}"


for n, k in [(40, 10), (100, 10), (100_000, 50)]:
    count = math.comb(n - 1, k - 1)
    shown = f"{count:,} splits" if count < 10**15 else f"{len(str(count))}-digit number of splits"
    print(f"{n:,} chapters, {k} students: {shown}, {duration(count * per_split) if count < 10**30 else 'far longer than the age of the universe'}")

k = 3: 65 after 10 splits
k = 1: 190 after 1 split
k = 3: -1 after 0 splits
k = 6: 60 after 1 split
28 chapters, 8 students: 888,030 splits, about 1.4 microseconds each
40 chapters, 10 students: 211,915,132 splits, about 5 minutes
100 chapters, 10 students: 1,731,030,945,644 splits, about 28 days
100,000 chapters, 50 students: 183-digit number of splits, far longer than the age of the universe

Each split costs a microsecond or two, so 40 chapters among 10 students already take minutes, 100 chapters take weeks, and the stated limits are out of reach for any computer.

What to notice

Fix a limit S on the pages any one student may read. If k students can cover the chapters within S, they can within any larger limit too, so “k students are enough for limit S” is false for small limits and true from one limit on. And one pass answers it for a given S: give the first student chapters while they fit, then the next student, and count the students used.

The smallest workable limit by halving, step by step Pro: opens with a Pro, Premium or Ultimate pass