Several approaches exist to this problem. The simplest solution is to simply count the number of guests present at the hotel for each time from 0 to 1000, and print the maximum. A guest is present if the current time is greater than or equal to their arrival time but less than their departure time.
For a better approach, call arrivals and departures “events”. Sort the 2*N events by the time at which they occur. In case of ties, place departures before arrivals. Then process the events in order, adding 1 to a count whenever an arrival occurs, and subrtacting 1 when a departure occurs, and print the maximum count.
This is a variant of interval selection problem. Sort the guest’s departure time in increasing order. Check for every guest with other guests, if departure time of this guest is greater than the arrival time of the other guests, increment the count. After completion of comparison of each guest with others update the max value. Max will give the number of guests present simultaneously.
start from hr=0; increase hour(hr++), if you encounter arrival(arr[i]) then increase guest(count++), if you encounter departure(dep[i]), then decrease guest(count–). meanwhile, keep record of maximum guest number(if(count>max) max=count). print out max.
I’m getting SIGSEGV error even though i have checked for proper array limits and otherwise used a vector.I have checked for arrival and departure time = 1000 too. Its working fine on my machine. Can someone please tell whats wrong with my code. Thanks in advance. http://www.codechef.com/viewsolution/3798769
I would appreciate some help identifying the error in my code - it looks to me to be doing the same thing as most of the accepted solutions. Thanks in advance.
from sys import stdin
from collections import Counter
T = int(stdin.readline().strip())
for _ in range(T):
N = int(stdin.readline().strip())
arrivals = map(int, stdin.readline().split(' '))
departures = map(int, stdin.readline().split(' '))
groups = zip(arrivals, departures)
occupation_groups = [list(range(group[0], group[1])) for group in groups]
occupations = Counter([num for group in occupation_groups for num in group])
print(max(occupations.values()))
import heapq
# cook your dish here
t = int(input())
for _ in range(t):
N = int(input())
arrival = list(map(int , input().split(" ")))
departure = list(map(int , input().split(" ")))
count=0
arr = [[arrival[i],departure[i]] for i in range(N)]
arr = sorted(arr, key=lambda x: x[0])
min_deparature = float("inf")
heap = []
result=0
for i in arr:
if i[0]<min_deparature:
count+=1
if i[1] >=min_deparature:
heapq.heappush(heap,i[1])
else:
heapq.heappush(heap,min_deparature)
min_deparature=min(min_deparature,i[1])
else:
result = max(result,count)
while i[0]>=min_deparature:
count-=1
min_deparature=heapq.heappop(heap)
count+=1
if i[1] >=min_deparature:
heapq.heappush(heap,i[1])
else:
heapq.heappush(heap,min_deparature)
min_deparature=min(min_deparature,i[1])
result = max(result,count)
#print(count,i,heap)
result=max(result,count)
print(result)