Theorem 9. The problem $1 \mid \mathrm{rep} \mid \min_j \sum_i Z_{i,j}$ is solvable in polynomial time when $k = m - 1$.

Associate with every day $i$ and client $j$ a variable $x_{i,j}$, read as "client $j$'s job is executed on day $i$". Two families of clauses express the two requirements. For every day $i$ and every two distinct clients $j_1, j_2$ whose jobs conflict on that day, the conflict clause $(\lnot x_{i,j_1} \lor \lnot x_{i,j_2})$ forbids executing both. For every client $j$ and every two distinct days $i_1, i_2$, the validation clause $(x_{i_1,j} \lor x_{i_2,j})$ forbids rejecting the client on both. A schedule satisfies the first family exactly when it is feasible and the second exactly when no client is rejected twice, which at $k = m-1$ is fairness. The formula is a 2-CNF formula of $mn$ variables and $mn^2 + nm^2$ clauses, and 2-satisfiability is decidable in linear time.

The parameter $k = m-1$ is exactly the value at which two literals suffice: "$j$ is served on at least $m-1$ days" says "of any two days, $j$ is served on one of them", a binary constraint.