14-1 Point of maximum overlap

Suppose that we wish to keep track of a point of maximum overlap in a set of intervals—a point with the largest number of intervals in the set that overlap it.

a. Show that there will always be a point of maximum overlap that is an endpoint of one of the segments.

b. Design a data structure that efficiently supports the operations $\text{INTERVAL-INSERT}$, $\text{INTERVAL-DELETE}$, and $\text{FIND-POM}$, which returns a point of maximum overlap. ($\textit{Hint:}$ Keep a red-black tree of all the endpoints. Associate a value of $+1$ with each left endpoint, and associate a value of $-1$ with each right endpoint. Augment each node of the tree with some extra information to maintain the point of maximum overlap.)