1. Your friend Maggie is charged with organizing the next Wipeout competition for which she must decide on the obstacles that should be set for the contestants participating. Maggie would like most of the obstacles chosen to be the favourites of the viewers. Luckily, she already has the data of past competitions from which she can extract such information. The data of n objects includes the following information: name of each obstacle and for each obstacle the number of viewers that prefer this obstacle over all others. From this data Maggie wants to pick the i obstacles that have the most number of viewers and rank them according to the number of views.

(a) Help Maggie to come up with an O(n + i logi)-time algorithm that finds the i obstacles that have the most number of views and are ranked in order of the number of views.

(b) b Justify the O(n +ilgi) time complexity of your algorithm.