Algorithm design. Each of $n$ users spends some time on a social lklkmedia site. For each

$i=1,$dots,$n,$ user i enters the site at time $a_i$ and leaves at time $b_i{a}_i.$ You are interested

in the question: how many distinct pairs of users are ever on the site at the same time?

$($Here$,$ the pair $(i,j)$ is the same as the pair $(j,i)).$

Example: Suppose there are $5$ users with the following entering and leaving times:

Then, the number of distinct pairs of users who are on the site at the same time is three:

these pairs are $(1,2),(4,5),(3,5).($Drawing the intervals on a number line may make

this easier to see$).$

$($a$)(10$ points$)$ Given input $(a_1,b_1),(a_2,b_2),$dots,$(a_n,b_n)$ as above in no particular order

$($i$.$e$.,$ not sorted in any way$),$ describe a straightforward algorithm that takes $(n^2)-$

time to compute the number of pairs of users who are ever on the site at the same

time, and explain why it takes $(n^2)-$time. $[$We are expecting pseudocode and

a brief justification for its runtime.$]$

Answer:

$($b$)(10$ points$)$ Give an $(nlog(n))-$time algorithm to do the same task and analyze its

running time. $($Hint: consider sorting relevant events by time$).[$We are expecting

pseudocode and a brief justification for its runtime.$]$

Answer: