Problem $5-4()$

$15$ points

You are a teacher at a preschool, and there are $n$ children in your class with happiness threshold

$h[1$:$n].$ You have $m>n$ chocolates with sizes $s[1$:$m].$ Each child should get exactly one chocolate.

If child $i$ is assigned chocolate $j$ and $h[i]s[j],$ that child is said to be "happy".

Name $($Name$),$ Homework $2,,$ Page $1$

$($a$)(5$ points$)$ Give a greedy algorithm to distribute chocolates to children so as to maximize the

number of happy children.

$($b$)(5$ points$)$ Prove that your algorithm is optimal.

$($c$)(5$ points$)$ Compute the time complexity of your algorithm.