Is there a function that is the envelope of the sum of ceilings of reciprocal functions

Question

TL;DR:

Given a sum of ceilings of reciprocal functions

$$y_1 = T = \sum^{n-1}_i \Big\lceil \frac{p_i}{k} \Big\rceil$$

is there a corresponding form for a function that envelopes the $T$ on the left? Or in other words, is there a form for the function $L$ that touches the left endpoint of each line segment in the graph of $y_1 = T$?

More formally,

Given $y_2 = h$ for some integer $h$, we have that $y_1$ and $y_2$ intersect in a line segment, say at $y=h$ from $x=x_{h^-}$ to $x=x_{h^+}$. The left envelope of $y_1 = T$ would be the function $L$ such that for each integer $h$, we have $L(x_{h^-}) = h$ or in other words for each integer $h$, we have $L(x) = h$ iff $x = x_{h^-}$.

For example, in this Desmos graph, we have

$$ y_1 = T = \Big\lceil \frac{3}{x} \Big\rceil + \Big\lceil \frac{6}{x} \Big\rceil + \Big\lceil \frac{7}{x} \Big\rceil + \Big\lceil \frac{11}{x} \Big\rceil $$

and $y_1 = T$ intersects $y_2 = h = 8$ in a line segment at $y = 8$ from $x=x_{h^-}=3.667$ to $x=x_{h^+}=5.5$. The left envelope of this $T$ would have $L(3.667) = 8$.

---

Given a sum of two reciprocals

$$ T_2 = \Big\lceil \frac{p_0}{k} \Big\rceil + \Big\lceil \frac{p_1}{k} \Big\rceil $$

we can note that $p_0 = ak + b$ and $p_1 = ck + d$ for some integers $0 \leq b, d < k$ and so we have

$$ \Big\lceil \frac{ak + b}{k} \Big\rceil = \begin{cases} a & \text{if } b = 0\\ a+1 & \text{if } b \neq 0 \end{cases} $$

and similarly for $p_1$.

Overall we have four cases for the value of $T_2$:

	$d = 0$	$d \neq 0$
$b = 0$	$a+c$	$a+(c+1)$
$b \neq 0$	$(a+1)+c$	$(a+1)+(c+1)$

Note, asking whether $b = 0$ or $b \neq 0$ is the same as asking whether $p_0$ is divisible by $k$ or not, respectively.

We can express the above in python3 as follows:

a, b = divmod(p[0], k)
c, d = divmod(p[1], k)
T = a + (b != 0) + c + (d != 0)

# Alternative
# T = a + bool(b) + c + bool(d)

Also, each time we add a $\big\lceil \frac{p_i}{k} \big\rceil$ term to the $T$ sum, we introduce two new cases (i.e. whether $p_i$ is divisible by $k$ or not). Thus a $T$ sum of $n$ terms would have $2^n$ cases. Is there any way around this? Perhaps there's a more clever way to combine terms...???

---

Motivating problem:

I was doing Leetcode #875: Koko Eating Bananas (description in footnote [1]).

The answer can be found using binary search over $k_{min} <= k <= k_{max}$ where k_min = sum(piles) / h and k_max = max(piles) (see footnote [2]), but I was wondering if there's an even more mathematical way to find it.

Having chosen a $k$, $p_i = $pile[i] takes $t_i = \big\lceil \frac{p_i}{k} \big\rceil$ hours to consume and all $n$ piles take

$$T = \sum^{n-1}_i \Big\lceil \frac{p_i}{k} \Big\rceil$$

hours to consume. We want to minimize $k$ such that $T \leq h$.

This can be done graphically:

---

Given example 1:

Input: piles = [3,6,7,11], h = 8
Output: 4

We graph

$$ \begin{aligned} y_1 = T &= \sum^{n-1}_i \Big\lceil \frac{p_i}{x} \Big\rceil\\ &= \Big\lceil \frac{3}{x} \Big\rceil + \Big\lceil \frac{6}{x} \Big\rceil + \Big\lceil \frac{7}{x} \Big\rceil + \Big\lceil \frac{11}{x} \Big\rceil \end{aligned} $$

where $p_i$ represents piles[i], $y$ represents T, and $x$ represents k. We also graph $y_2 \leq h$ to represent the constraint. The minimum value of $k$ is minimum value of $x$ where $y_1$ and $y_2$ intersect.

See the Example 1 Desmos graph, which shows the minimum value of $k$ is $3.667$, though since the problem statement calls for $k$ being an integer, the actual value is $4$.

---

Here is another examples:

Input: piles = [30,11,23,4,20], h = 6
Output: 23

Likewise, here's the Example 3 Desmos graph, which shows the minimum value of $k$ is $23$.

---

[1]: Leetcode #875: Koko Eating Bananas

Koko loves to eat bananas. There are $n$ piles of bananas, the $i$th pile has piles[i] bananas (piles is $0$-indexed). The guards have gone and will come back in $h$ hours.

Koko can decide her bananas-per-hour eating speed of $k$. Each hour, she chooses some pile of bananas and eats $k$ bananas from that pile. If the pile has less than $k$ bananas, she eats all of them instead and will not eat any more bananas during this hour.

Koko likes to eat slowly but still wants to finish eating all the bananas before the guards return.

Return the minimum integer $k$ such that she can eat all the bananas within $h$ hours.

[2]: Binary Search solution

class Solution:
    def minEatingSpeed(self, piles: List[int], h: int) -> int:
        k_min = (sum(piles) + h-1) // h # ceil(sum(piles) / h) 
        k_max = max(piles)
        
        l, r = k_min, k_max + 1
        while l < r:
            k = (l+r) // 2
            t = sum((p + k-1) // k for p in piles) # sum(ceil(p / k) for p in piles)
            if t <= h:
                r = k
            else: # t > h
                l = k + 1
        return l