Answer Happy

Laura has a concert coming up, and in preparation, she wants to
learn as many
pieces as possible. There are m possible pieces she could learn.
Each piece i takes pi
hours to learn. Laura has a total of T hours that she can study by
herself (before getting
bored). In addition, she has n vocal coaches. Each teacher j will
spend up to tj hours
coaching. The coaches are very strict, so they will teach Laura
only a single piece, and
only if no other coach is teaching her that piece. Thus, to learn
piece i, Laura can
either (1) learn it by herself by spending pi of
her T self-learning budget; or (2) she can
choose a unique coach j (not chosen for any other piece), learn
together for min {pi , tj}
hours, and if any hours remain (pi >
tj), learn the rest using pi − tj hours of her T
self-
learning budget. (Learning part of a piece is useless.)
a) Assume that Laura decides to learn exactly k pieces. Prove that
she needs to
consider only the k lowest pi s and the k highest
tj s.

b) Assuming part (a), give an efficient greedy algorithm to
determine whether
Laura can learn exactly k pieces. Argue its correctness.