Duration of maximum number of overlapping events
While trying to improve my algoritmic skills I have found myself stuck in the following problem which in short asks you to find the duration of the timespan where there are a maximum number of people present in a room:
https://jutge.org/problems/P27158_en
The solution I have come up with solves the problem correctly for all the public test cases suggested by the website, but it fails for one or more hidden private test cases.
My solution saves two entries for each event in a std::vector: one for the arrival and one for the leaving, each consisting of [eventtype, eventtime]. Then sorts the vector by the eventtime, and finally loops through the vector to determine the duration of the timespan where there are a maximun number of guests. My code is as follows:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
enum class EventType {ARRIVE, LEAVE};
struct Event{
int time;
EventType type;
Event(){}
Event(int tm, EventType t) : time(tm), type (t){}
// inline bool operator<(const Event& e) const {return time < e.time || (time == e.time && type==EventType::LEAVE);}
};
bool eventCompare(const Event& e1, const Event& e2) {
if(e1.time < e2.time){
return true;
} else if(e1.time == e2.time) {
if(e1.type == EventType::LEAVE && e2.type == EventType::ARRIVE) {
return true;
} else {
return false;
}
} else {
return false;
}
}
int main()
{
int visits;
int timeStart, timeEnd;
int maxVisits, maxDuration, localMaxVisits, localStartTime, localEndTime, duration;
std::vector<Event> events;
std::vector<Event>::const_iterator it;
// Get each Case from stdin.
// 0 is the special stopping case.
while(cin>>visits && visits!=0) {
events.clear();
// Read all the visits, for each one save two entries to the visits-vector,
// one for the arrival time another for the leaving time.
for(int i=1; i<=visits; ++i){
cin>>timeStart>>timeEnd;
Event eStart(timeStart, EventType::ARRIVE);
Event eEnd(timeEnd, EventType::LEAVE);
events.push_back(eStart);
events.push_back(eEnd);
}
// Sorting the vector so that events are ordered by their arrival time.
// In case two events coincide on arrival time, we place leaving events before arrival events.
std::sort(events.begin(), events.end(), eventCompare);
maxVisits=0;
maxDuration=0;
localMaxVisits=0;
localStartTime=0;
localEndTime=0;
// Loop through the sorted vector
for(it=events.begin(); it!=events.end(); ++it){
// If the event type is arrival
if((*it).type == EventType::ARRIVE) {
// We only reset the localStartTime if there is no
// gap between the last endtime and the current start time
// For example two events 11-13 and 13-15 should be treated as one long event
// with duration 11-15
if(localEndTime < (*it).time) {
localStartTime = (*it).time;
}
localMaxVisits++;
} else { // Event type leave
// Calculate the duration
duration = (*it).time - localStartTime;
// If we have a new max in overlaps or equal overlaps but larger duration than previous
// We save as the global max.
if(localMaxVisits > maxVisits || (localMaxVisits == maxVisits && duration>maxDuration)) {
maxVisits=localMaxVisits;
maxDuration = duration;
}
localMaxVisits--;
localEndTime= (*it).time;
}
}
cout<<maxVisits<<" "<<maxDuration<<endl;
}
return 0;
}
I have modified the code accordingly to the comment from @j_random_hacker and the program now does not exceed time limit as it did before for the hidden private test cases, but now gets a verdict "Wrong answer" (only for the private test cases). I will try and find out what the algorithm error may be. Thanks everyone who answered.
I changed the comparison function to this and the TLE went away (and changed to a WA):
bool operator< ( const Event& e ) const
{
return (time < e.time) || (time == e.time && type==EventType::LEAVE && e.type != EventType::LEAVE);
}
The reason for this, as suggested in the comments, is that the comparison function you gave did not have a strict weak ordering. (It returned true even when the two objects had the same time and the same type ( EventType::LEAVE ), whereas it should have returned false when both the objects are equivalent.)
EDIT:
You are getting WA because of test cases like these:
5 1 3 1 3 3 4 4 7 4 7
Your output - 2 6
Correct output - 2 3
You are getting the maximum number of events right but their durations wrong.
The remedy for this is to to calculate the answer in two iterations.
In the first iteration, we calculate the maximum number of events.
In the second iteration, we calculate the maximum duration using the result obtained in the first iteration.
The correct code (almost similar to yours) :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
enum class EventType {ARRIVE, LEAVE};
struct Event
{
int time;
EventType type;
Event() {}
Event ( int tm, EventType t ) : time ( tm ), type ( t ) {}
bool operator< ( const Event& e ) const
{
return ( time < e.time ) || ( time == e.time && type == EventType::LEAVE &&
e.type != EventType::LEAVE );
}
};
int main()
{
int visits;
int timeStart, timeEnd;
int maxVisits, maxDuration, localMaxVisits, localStartTime, localEndTime,
duration;
std::vector<Event> events;
std::vector<Event>::const_iterator it;
// Get each Case from stdin.
// 0 is the special stopping case.
while ( cin >> visits && visits != 0 )
{
events.clear();
// Read all the visits, for each one save two entries to the visits-vector,
// one for the arrival time another for the leaving time.
for ( int i = 1; i <= visits; ++i )
{
cin >> timeStart >> timeEnd;
Event eStart ( timeStart, EventType::ARRIVE );
Event eEnd ( timeEnd, EventType::LEAVE );
events.push_back ( eStart );
events.push_back ( eEnd );
}
// Sorting the vector so that events are ordered by their arrival time.
// In case two events coincide on arrival time, we place leaving events before arrival events.
std::sort ( events.begin(), events.end() );
maxVisits = 0;
localMaxVisits = 0;
// Find `maxVisits`
for ( it = events.begin(); it != events.end(); ++it )
{
if ( ( *it ).type == EventType::ARRIVE )
{
localMaxVisits++;
}
else
{
maxVisits = max ( maxVisits, localMaxVisits );
localMaxVisits--;
}
}
maxDuration = 0;
localStartTime = 0;
localEndTime = 0;
// Now calculate `maxDuration`
for ( it = events.begin(); it != events.end(); ++it )
{
if ( ( *it ).type == EventType::ARRIVE )
{
localMaxVisits++;
if ( localMaxVisits == maxVisits && localEndTime < ( *it ).time )
{
localStartTime = ( *it ).time;
}
}
else
{
duration = ( *it ).time - localStartTime;
if ( localMaxVisits == maxVisits )
{
localEndTime = ( *it ).time;
maxDuration = max ( maxDuration, duration );
}
localMaxVisits--;
}
}
cout << maxVisits << " " << maxDuration << endl;
}
}
You can simplify your code by doing away with the Event class altogether, and using pair<int,int> instead. Pairs are sorted by their first element (which would be your event time) and then by their second. I propose populating your vector with code similar to:
vector<pair<int,int>> v;
for (int i=0; i<n; i++) { // n events to add
int a, b;
cin >> a >> b;
v.push_back({a, 1}); // 1 for "enter"
v.push_back({b, -1}); // -1 for "leave"
}
sort(v.begin(), v.end());
As you can see, sorting does not require anything extra to be defined. It just works (tm).
Two pitfalls:
I can also confirm that, for this particular problem, the judge won't accept any answer that uses complex structures (I initially tried to solve it with a map<int, int> ). Simply performing
map<int,int> m;
for (int i=0; i<n; i++) { // n events to add
int a, b;
cin >> a >> b;
m[a]++; // add 1 party-goer at time a
m[b]--; // remove 1 at time b
}
gets you a time-limit-exceeded (even though it sorts itself automatically). So even if interval trees are great for repeated interval queries, they are not the right tool for this particular problem (which queries only once).
Good luck fixing your code for that elusive AC! I can confirm that it is attainable.
链接地址: http://www.djcxy.com/p/32506.html上一篇: 如何使用Python在相同的TCL shell上运行命令
下一篇: 重叠事件的最大次数的持续时间