Maximum Simultaneous Museum Visitors
National Olympiad — National round (2018 season)
Submission name: visitors.cpp
Problem summary
Find maximum simultaneous occupancy during one day from visitors’ arrival and departure times. Departure seconds are included.
Input
N, then N arrival/departure pairs HH:MM:SS.
Output
Maximum occupancy.
Constraints
0 ≤ N ≤ 1000; valid within-day stays.
Worked example
Input and output for the worked example discussed below.
Input
4 08:00:00 10:00:11 09:00:23 14:00:06 11:00:52 13:00:24 11:15:17 13:15:08
Output
3
Solution analysis
- Convert a timestamp to 3600×hours+60×minutes+seconds. One day has only 86400 second positions.
- Add +1 at arrival and −1 at departure+1 in a difference array. Prefix sums then count each visitor at exactly the inclusive seconds of the stay.
- Sample visitors 2,3,4 overlap from 11:15:17 through 13:00:24, giving maximum 3. An empty visitor list gives zero.
Why it works
The difference-array contribution is one exactly over each included stay.
Complexity: O(N+86400) time and O(86400) space.
Watch out. Reserve index 86400 for the sentinel following 23:59:59. Parse minutes and seconds as well as hours.
Commented C++17 solution
An independently written complete program with standard headers.
// The difference-array contribution is one exactly over each included stay.
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int seconds(const string&time){
return stoi(time.substr(0,2))*3600+stoi(time.substr(3,2))*60+stoi(time.substr(6,2));
}
int main(){
int visitors;
cin>>visitors;
vector<int>difference(86401);
while(visitors--){
string arrival,departure;
cin>>arrival>>departure;
difference[seconds(arrival)]++;
difference[seconds(departure)+1]--;
}
int current=0;
int answer=0;
for(int second=0;second<86400;second++){
current+=difference[second];
answer=max(answer,current);
}
cout<<answer<<'\n';
}