Problem $2$: Bear Island $(30$ pt$.)$

One day, you get stranded on a beach on an island with n bears. You will be here a while, so you want to make friends and introduce yourself to all the bears. However, you don$$t want to leave the beach since the rest of the island looks dangerous. Each bear i will only be on the beach during one time interval $[$ai$,$ bi$],$ inclusive. You can only introduce yourself to bear i during this time interval.

Your plan is to stand in the center of the beach and use the megaphone you brought with you to say $$Hello$$ at certain times t$1,...,$ tm$.$ Any bear on the beach at one of the times tj in $\{$t$1,...,$ tm$\}$ will hear your introduction. It$$s okay if a bear hears your introduction more than once, but you want to make sure every bear hears your introduction at least once.

$$

$5\mathrm{.}1$ Greedy Algorithm $(10$ pt$.)$

The battery in your megaphone is low, so you want to minimize m$,$ the number of times you use your megaphone. Devise a greedy algorithm that takes as input the list of intervals $[$ai$,$ bi$]$ and outputs a list oftimes t$1,...,$ tm such that m is as small as possible but every bear hears your introduction. Your algorithm should run in time O$($n log n$)$ where n is the number of bears on the island. You can assume every bear visits the beach at some point.

$[$We are expecting: Pseudocode and an English description of your algorithm, as well as a short justification of the runtime$]$

$$

$5\mathrm{.}2$ Proof of Correctness $(10$ pt$.)$

Give a formal proof that your algorithm is correct.