Theorem 10. Let $I$ be an instance all of whose processing times are $1$ and let $k \le m$. Consider the bipartite graph whose one side holds a vertex $v_{i,j}$ for every day $i$ and client $j$, and whose other side holds a vertex $u_{i,t}$ for every day $i$ and time $t$ together with $m - k$ vertices $w_{1,j}, \ldots, w_{m-k,j}$ for every client $j$; join $v_{i,j}$ to $u_{i,d_{i,j}}$ and to all $m-k$ vertices $w_{\cdot,j}$. Then $I$ admits a $k$-fair schedule if and only if this graph has a matching saturating every vertex $v_{i,j}$.

With unit processing times two jobs of a day conflict exactly when their due dates agree, so a day's machine may execute at most one job per due date; matching $v_{i,j}$ to $u_{i,d_{i,j}}$ records that client $j$ is served on day $i$, and matching it to one of the $m-k$ vertices $w_{\cdot,j}$ records that it is not. A matching saturating the job side thus assigns every job either a slot of its day or one of the $m-k$ rejections client $j$ is allowed.