example data structure format for 4.3:

error while writing the assignment, the complexity should be and not worst-case). Some of the cost of processing the next visitor can be shared with previous visitors. onsider pairs (xi,yi) such that xi is the time at which person i=0,1,2, enters the museum and yi is the time at which person i leaves the museum. You may assume that consecutive people enter the museum in order of increasing time (x0x1). P4.1. Provide an algorithm MaxVisirors that takes as input L=[(x0,y0),,(xN1,yN1)] and computes in NlogN the maximum number of visitors in the museum at any time. P4.2. Argue why your algorithm MaxVisirors is correct and has a runtime complexity of NlogN. P4.3. Assume that the museum has a maximum capacity of M. Provide a datastructure with an operation PersonEnters(xi,yi) that computes in at-most logM the number of visitors in the museum when person i enters the museum (for any number of persons). P4.4. Argue why your algorithm PersonEnters is correct and has a runtime complexity of logM. Algorithm Sink(L[0N),p) : 1: while true do 2:3:4:5:6:np:=rchild(p).7:ifnp=pthenreturn.8:ExchangeL[p]andL[np].9:np:=p.np:=p.iflchild(p)