We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
fromcollectionsimportdefaultdictfromdataclassesimportdataclass,fieldimportheapqclassEventType:# order matters; for events on the same position,# process start then town then endCloudStart=1Town=2CloudEnd=3@dataclass(order=True)classEvent:# order matters; for events on the same position,# process start then town then endpos:int=field(compare=True)t:EventType=field(compare=True)popn:int=field(default=0,compare=False)defmaximumPeople(p,x,y,r):all_events=[]for(pos,popn)inzip(x,p):heapq.heappush(all_events,Event(pos,EventType.Town,popn=popn))foridx,(pos,rd)inenumerate(zip(y,r)):heapq.heappush(all_events,Event(pos-rd,EventType.CloudStart))heapq.heappush(all_events,Event(pos+rd,EventType.CloudEnd))always_sunny=0curr_active_cloud=set()cloud_pop_map=defaultdict(int)whileall_events:# sorted by pos then typee=heapq.heappop(all_events)matche.t:caseEventType.CloudStart:curr_active_cloud.add(e.cloud_idx)caseEventType.CloudEnd:curr_active_cloud.discard(e.cloud_idx)caseEventType.Town:iflen(curr_active_cloud)==1:cloud_pop_map[list(curr_active_cloud)[0]]+=e.popneliflen(curr_active_cloud)==0:always_sunny+=e.popnoverall_max=max(cloud_pop_map.values()or[0])returnalways_sunny+overall_max
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Cloudy Day
You are viewing a single comment's thread. Return to all comments →