Duration of maximum number of overlapping events

Question

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.

Answer 1

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;
    }
}

Answer 2

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:

• if I arrive at t0, and somebody else leaves at t0, the number of people in the party has not changed.
• if many people arrive or leave at exactly the same time, you should only re-calculate change-in-assistance once (and if it is 0, ignore it altogether, as in the previous pitfall).

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.