Question $5$: Let $m$ be a large integer and consider $m$ non$-$empty sorted lists $L_1,L_2,$dots,$L_m.$

All numbers in these lists are integers. Let $n$ be the total length of all these lists.

Describe an algorithm that computes, in $O(nlogm)$ time, two integers a and $b,$ with

$ab,$ such that

each list $L_i$ contains at least one number from the set $\{a,a+1,$dots,$b\}$ and

the difference $b-a$ is minimum.

For example, if $m=4,$

$L_1=(2,3,4,8,10,15)$

$L_2=(1,5,12)$

$L_3=(7,8,15,16)$

$L_4=(3,6),$

then the output can be $(a,b)=(4,7)$ or $(a,b)=(5,8).$

As always, justify the correctness of your algorithm and explain why the running time is

$O(nlogm).$

Hint: Use a min$-$heap of size $m$ and use Question $4.$ For the example, draw it like this, then

stare at it until you "see" the algorithm: