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.

Hymanhymen

The algorithm looks good to me. Did you profile what's taking it so long? Is it the std::sort() or something else? Or did you compile it without compiler optimizations and they aligned the run time limits to optimized programs? – Bunyip

I have not tried to profile the execution, but searching documentation I concluded that the std::sort should be the fastest way of sorting a vector. In other words, even if I find that the std::sort takes a relatively long time in large datasets I would not know which sorting algorithm I should use instead. But you are right, I should check wich part of the code is the main time consumer. As to the your other question, I only submit the source code to the test site, so I have no idea with which compiler settings they compile and later execute my program. – Hymanhymen

I think the sort shouldn't be the first place you should be looking at to speed up your algorithm. Instead, I believe the content of your loops is much more crucial to the speed of your algorithm. However, as Heinzi has pointed out, profiling will definitely help you quite a bit in identifying the bottleneck of your algorithm. – Grayish

Pardon me if I'm wrong but the algorithm seems to be of O(n). – Grayish

std::sort() needs a comparison function that describes a total order, but the one you give can say that both a < b and b < a are true if their times are equal and the leftmost one is a LEAVE. This could in theory (and even in practice) cause std::sort() to crash or hang. – Mendes

@Grayish The algorithm is O(nlogn) because of std::sort – Bunyip

@Bunyip Isn't the sort outside of the loop that represents the n in O(n)? I believe that would make it O(n + logn) which pretty much simplifies to O(n). – Grayish

The sort itself takes O(nlogn), not O(logn) – Bunyip

#3755878 – Kanarese

@Bunyip I see! Now I get why you are focusing on the sort. Thanks! – Grayish

@Mendes you are right, I have changed code so that the sort uses a comparison function (code updated in the original post). The code still works with all public test cases but now it fails with a verdict "wrong answer" for one or more hidden test cases. So I suppose that there is some error in my general algorithm that I will need to find. – Hymanhymen

Instead of sorting after, perhaps do sorted insert. – Mantling

@MadPhysicist sorted insert is worse for vectors, because if you discover something that has to go to the front, you have to shift elements around, in O(n) for the worst case. A final sort will have a much lower runtime, because only swapping is required: no shifts, ever. – Sideslip

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

Foltz

Yes, I did the same, see my last comment on the original post. – Hymanhymen

@Hymanhymen Okay. You should also modify the question accordingly then. – Foltz

@Hymanhymen Check the answer now. – Foltz

Ok @Anmol Singh Jaggi, thanks for looking into it, so it seems that my basic aproach really was an error prone one. – Hymanhymen

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.

Sideslip

Thanks @Sideslip for your suggestions. By the way are you sure that your time limit problem using a map was because jutge doesn´t allow complex structures, could it not have been because your (first) solution simply wasn´t right? – Hymanhymen

The problem is not that maps are "complex"; it is that they are much slower than vectors to populate, even if you later have to sort the vector. My test was to hard-code correct values for the sample input, and replay them one-by-one regardless of input (guaranteeing AC for the public testcases) - once using the code snippet above (WA for private testcases), and once using the code-snippet below (TLE for private). I think that is a pretty conclussive test. – Sideslip