Compression Bounds - Determine and Visualize for hypothesis vs VC dimension
Generally, every class of finite VC dimension admits to a (exponential size in the dimension) compression scheme. This was an open question resolved a few years ago by Shay and Amir in this paper. However, this is an overkill for your question, since $H_k$ obviously has a $k$-comprresion scheme (only keep the samples labeled $1$, of which there are at most $k$, and the reconstruction is zero everywhere else).
$H_{desct}$ can be compressed to two samples, given $\left((a_i,b_i),y_i\right)_{i=1}^n$, we know that either there exists $j$ such $\forall i\in[n]: y_i=\mathbb{1}_{a_i\le a_j}$ or there exists $j$ such that $\forall i\in[n] : y_i=\mathbb{1}_{b_i\le b_j}$. The compression keeps $(a_j,b_j)$ and one more sample $(a_{j'},b_{j'})$ to indicate the correct coordinate of the threshold, e.g. if the former condition holds and $\forall i\in[n]: y_i=\mathbb{1}_{a_i\le a_j}$ then pick $j'$ such that $y_{j'}\neq y_j$ (so $y_{j'}=0)$ and $b_{j'}&lt;b_j$ (this allows us to reconstruct the function $\mathbb{1}_{x_1\le a_j}$ from the two samples). If no such $j'$ exists then $\mathbb{1}_{x_2\le b_j}$ is also a consistent hypothesis, and our compression can keep only one sample.