Solução escrita por Levi Oliveira
Para maximizar a quantidade de cupons, é interessante parearmos valores cuja diferença não seja muito grande. Suponha que os valores dados sejam ordenados de forma que $v_1 \leq v_2 \leq v_3 \leq v_4$.
Inicialmente, note que nunca vale a pena formar os pares ${v_1,v_3}$ e ${v_2,v_4}$. Isso acontece porque, como $v_3 \geq v_2$, temos que $v_3-v_1 \geq v_2-v_1$, e, como $v_4 \geq v_3$, temos que $v_4-v_2 \geq v_4-v_3$.
Portanto, devemos escolher entre os pares ${v_1,v_2}$ e ${v_3,v_4}$ ou os pares ${v_1,v_4}$ e ${v_2,v_3}$.
Podemos ordenar os valores e analisar qual dessas opções permite obter a maior quantidade de cupons.
OBS: O único caso em que valerá a pena formar o par ${v_2,v_3}$ é quando $v_2-v_1 > k$. Isso acontece porque, como $v_2$ é o próximo menor valor disponível, $v_1$ não conseguirá formar um par válido. Assim, ao escolher com quem $v_2$ irá parear, sempre valerá mais a pena pareá-lo com $v_3$, em vez de $v_4$.
Complexidade: $O(1)$, após a ordenação.