HOTEL - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

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.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

4 Likes

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.

4 Likes

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.

3 Likes

I keep getting Time Limit Exceeded with Python even though I did what you said. Here’s my solution http://www.codechef.com/viewsolution/3787067

1 Like

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

1 Like

Getting WA .

http://www.codechef.com/viewsolution/5210479

Please help

1 Like