c++ - 最大重叠事件数的持续时间

Question

在尝试提高我的算法技能时，我发现自己陷入了以下问题，简而言之，它要求您找出房间中出现最大人数的时间跨度的持续时间:

https://jutge.org/problems/P27158_en

我提出的解决方案对网站建议的所有公开测试用例都正确解决了问题，但对一个或多个隐藏的私有(private)测试用例却失败了。

我的解决方案为 std::vector 中的每个事件保存了两个条目:一个用于到达，一个用于离开，每个都由 [eventtype, eventtime] 组成。然后按事件时间对 vector 进行排序，最后循环遍历 vector 以确定存在最大客人数的时间跨度的持续时间。我的代码如下:

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

我已经根据@j_random_hacker 的评论修改了代码，程序现在不会像以前那样对隐藏的私有(private)测试用例超过时间限制，但现在得到一个“错误答案”的判决(仅适用于私有(private)测试个案)。我会尝试找出算法错误可能是什么。感谢所有回答的人。

Answer 1

我将比较函数更改为此，TLE 消失了(并更改为 WA):

bool operator< ( const Event& e ) const
{
    return (time < e.time) || (time == e.time && type==EventType::LEAVE && e.type != EventType::LEAVE);
}

如评论中所述，这样做的原因是您提供的比较功能没有 strict weak ordering . (它返回 true，即使两个对象具有相同的 time 和相同的 type(EventType::LEAVE ), 而当两个对象相等时它应该返回 false。)

编辑:

由于像这样的测试用例，您获得了 WA:

5 1 3 1 3 3 4 4 7 4 7

你的输出 - 2 6
正确的输出 - 2 3

您得到的事件的最大数量是正确的，但它们的持续时间是错误的。

对此的补救方法是在两次迭代中计算答案。
在第一次迭代中，我们计算最大事件数。
在第二次迭代中，我们使用第一次迭代中获得的结果计算最大持续时间。

正确的代码(和你的差不多):

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