Dialling in the data cap

A small internet provider has bought a fixed amount of transit and wants its billed traffic to land on that number. Its only dial is the per-line cap.

The problem

Each customer line used some number of gigabytes last month, recorded in lines. The provider is choosing one cap for every line: a line under the cap is billed what it used, a line over it is billed the cap. So the billed total at cap c is the sum of min(used, c) across the lines.

The provider has committed to commitment gigabytes of transit and wants the billed total as close to that as possible — over or under does not matter, only distance. If two caps are equally close, return the smaller one: a lower cap is easier to defend to customers. The cap is a whole number of gigabytes and never needs to exceed the largest line.

Input. lines — a list of integers, gigabytes used per line. commitment — the target billed total.

Output. The cap whose billed total is closest to commitment, smaller cap on a tie.

Example.

lines = [40, 90, 120, 300], commitment = 320   ->  95

At a cap of 95 the bills are 40, 90, 95 and 95: exactly 320. At 90 the total is 310 and at 100 it is 330, both further away.

A second example, where no cap is exact:

lines = [10, 20, 30], commitment = 45   ->  17

A cap of 17 bills 44 and a cap of 18 bills 46: both one away, so the smaller wins. 46 is the first total to reach the commitment, so the crossing point alone is the wrong answer here.

Constraints.

• 1 <= len(lines) <= 10^4
• 1 <= lines[i] <= 10^5
• 0 <= commitment <= 10^9

Hints

Approach

Brute force

Try every cap from 0 to the largest line, summing the bill each time: with 100,000 gigabytes on the biggest line and 10,000 lines, 10⁹ additions.

The insight

Raising the cap never lowers the billed total, so "billed total is at least the commitment" is monotone — binary search the crossing, then compare it with the cap one below.

min(used, c) is non-decreasing in c, so the sum is too, and the caps read false, false, then true forever — the precondition binary search needs. But the crossing is the smallest cap that reaches the commitment; the cap just below is the last one under it, and no third cap can beat those two.

Algorithm

1. If capping at the largest line still bills under the commitment, return it — the total can go no higher.
2. Binary search lo = 0, hi = max(lines) for the smallest cap whose billed total reaches the commitment.
3. If that cap is 0, return 0.
4. Measure how far the crossing cap overshoots and how far the cap below it undershoots.
5. Return the crossing cap only if it is strictly closer; otherwise the one below, which also settles ties.

Complexity

Time O(n log m), with m the largest line — about 17 halvings, each summing all n lines. Space O(1).

Solution

"""Data cap dial — binary search the cap, then weigh the two candidates around it."""


def billed(lines, cap):
    """Gigabytes billed at this cap: a line over the cap is charged the cap."""
    return sum(min(used, cap) for used in lines)


def solve(lines, commitment):
    top = max(lines)
    if billed(lines, top) <= commitment:
        return top                     # even an uncapped month stays under the deal

    # P(cap) = "billed(cap) >= commitment" is monotone: raising the cap never
    # lowers the bill, so the caps read False ... False True ... True.
    lo, hi = 0, top
    while lo < hi:                     # invariant: the first True cap is in [lo, hi]
        mid = (lo + hi) // 2
        if billed(lines, mid) >= commitment:
            hi = mid
        else:
            lo = mid + 1
    if lo == 0:
        return 0

    # Binary search finds where the total crosses the commitment, not where it is
    # closest. Only the crossing cap and the one below it can win; ties take the lower.
    over = billed(lines, lo) - commitment
    under = commitment - billed(lines, lo - 1)
    return lo if over < under else lo - 1

TESTS = [
    (([40, 90, 120, 300], 320), 95),
    (([10, 20, 30], 45), 17),          # 44 and 46 are both 1 away; the lower cap wins
    (([25, 60, 15], 500), 60),         # commitment out of reach: cap at the top line
    (([7], 3), 3),
    (([10, 20], 0), 0),                # a cap of zero bills nothing
    (([40, 90, 120, 300], 550), 300),
]

Pitfalls

• Returning the crossing cap answers "first to reach the commitment", not "closest". On the second example that prints 18 instead of 17.
• Breaking ties toward the larger cap prints 18 there too. Use a strict comparison so an equal distance falls through to the lower cap.
• Assuming the commitment is reachable. When every line together bills under the commitment, no cap makes the predicate true and the loop's answer is accidental. Handle that case before searching.

Variants

• The autoclave load — the same monotone dial, but the crossing point itself is the answer, with no second check.
• Finding the accession — the same first-true search over positions rather than over a numeric dial.