Chapter 14, Problem 1P

(a)

Program Plan Intro

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

Explanation of Solution

Given Information: A point of maximum overlap in a set of intervals is a point with the largest number of intervals in the set that overlap it.

Explanation:

Consider that there is no point of maximum overlap in an endpoint of a segment. The maximum overlap occurs in the interior of m segments. Here, the point P is the intersection of those m points.

There must be another point $P^{\prime }$ that has the same overlap as P . Therefore, the point $P^{\prime }$ is also a point of maximum overlap. Hence, the assumption is not true since there is a point of maximum overlap in an endpoint of maximum overlap.

Hence, it is proved that the there is always a point where maximum overlap has an endpoint of the segment.

(b)

Program Plan Intro

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

Explanation of Solution

Explanation:

Consider a balanced binary tree of endpoints. For inserting the interval, it is necessary to insert the endpoints separately. Consider the endpoints as e . For left endpoint e , increase the value of e by 1 and for right endpoint e , decrease the overlap by 1.

For multiple endpoints with same value, insert the left endpoints with the value before the right endpoints with the value.

Consider that $e_1,e_2,\dots ,e_n$ be the sequence of the endpoints and $s\left(i,j\right)$ represents the sum. Therefore,

  $p\left[e_1\right]+p\left[e_{i+1}\right]+\dots +p\left[e_j\right]$

Where $1\le i\le j\le n$ .

Here, each node x store the new node that includes the endpoints $e_1\left[x\right],\mathrm{...},e_r\left[x\right]$ . The sum of the values of all nodes is stored as $v\left[x\right]=s\left(1\left[n\right],r\left[x\right]\right)$ and the maximum value id obtained by $s\left(1\left[n\right],r\left[x\right]\right)$ .

For bottom up approach to satisfy the conditions of red black tree following conditions must be hold:

  $m\left[x\right]=\max \{\begin{array}{l}m\left[\text{left}\left[x\right]\right]\\ v\left[left\left[x\right]\right]+p\left[x\right]\\ v\left[left\left[x\right]\right]+p\left[x\right]+m\left[right\left[x\right]\right]\end{array}$