Minimum Throughput to Finish a Backfill on Time

Pattern: Binary Search · Difficulty: Medium · Asked at: Amazon, Google, Databricks

Classic version: LeetCode 1011 · LeetCode 410

Problem

A backfill consists of partitions that must be processed in order; sizes[i] is the size of partition i in GB. Each day the cluster processes consecutive partitions up to a daily capacity C GB (a partition can’t be split across days). Return the minimum integer C that finishes all partitions within days days.

Examples

min_capacity([1,2,3,4,5,6,7,8,9,10], 5) → 15   # [1-5] [6,7] [8] [9] [10]
min_capacity([3, 2, 2, 4, 1, 4], 3)     → 6
min_capacity([1, 2, 3, 1, 1], 4)        → 3

Constraints

• 1 ≤ days ≤ len(sizes) ≤ 5·10⁴, 1 ≤ sizes[i] ≤ 500.

Starter code

def min_capacity(sizes: list[int], days: int) -> int:
    pass

Hints

Where this shows up in data engineering

This is literally capacity planning: “what’s the smallest cluster/throughput that completes this ordered backfill by the deadline?” The same shape answers “minimum Kafka consumer throughput to drain the lag within an hour” and “the smallest file-size target that keeps the number of output files ≤ N”.

Solution

def min_capacity(sizes: list[int], days: int) -> int:
    def days_needed(cap: int) -> int:
        used, load = 1, 0
        for s in sizes:
            if load + s > cap:          # start a new day
                used += 1
                load = 0
            load += s
        return used

    lo, hi = max(sizes), sum(sizes)     # below max(sizes) a partition never fits
    while lo < hi:
        mid = (lo + hi) // 2
        if days_needed(mid) <= days:
            hi = mid                    # feasible: try smaller
        else:
            lo = mid + 1
    return lo

Tests

Your solution should pass these:

assert min_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5) == 15
assert min_capacity([3, 2, 2, 4, 1, 4], 3) == 6
assert min_capacity([1, 2, 3, 1, 1], 4) == 3
assert min_capacity([10], 1) == 10
assert min_capacity([1, 1, 1, 1], 4) == 1
assert min_capacity([7, 2, 5, 10, 8], 2) == 18

Explanation

Two ideas combined:

1. Feasibility is greedy: packing each day as full as possible never needs more days than any other packing (exchange argument). O(n) per check.
2. Feasibility is monotonic in C: if C works, C+1 works. So binary search for the first feasible C.

Bounds: lo = max(sizes) (the largest partition must fit in a day), hi = sum(sizes) (one day does everything).

Complexity: O(n · log(sum − max)).

Recognising the pattern: the question asks for “the minimum X such that something is possible”, and checking a given X is easy. That combination almost always means binary search on the answer.

Follow-up questions