HOTEL - Editorial

editorial
, , ,
1

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
2

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.

5 Likes
3

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
4

I keep getting Time Limit Exceeded with Python even though I did what you said. Here’s my solution CodeChef: Practical coding for everyone

1 Like
5

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
6

Getting WA .

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

Please help

1 Like
7

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()))
8

Please check what is wrong in this code , It is clearly passing the base case given but when I submitted it ,it gave an error.

#include<bits/stdc++.h>
using namespace std;



int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		int ans[1001]={0};

		int guests;
		cin>>guests;

		int arrival[guests+1];
		int departure[guests+1];

		for(int i=1;i<=guests;i++)
		{
			cin>>arrival[i];
		}
		int min=*min_element(arrival+1,arrival+(guests+1));
	

		for(int i=1;i<=guests;i++)
		{
			cin>>departure[i];
		}
		int max=*max_element(departure+1,departure+(guests+1));




		for(int i=min;i<=max;i++)
		{
			for(int j=min;j<=guests;j++)
			{
				if(arrival[j]<=i && departure[j]>i)
				{
					ans[i]++;
				}
			}


		}


		int maxpeople=*max_element(ans+min,ans+max+1);
		cout<<maxpeople<<endl;


	}
	
}