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

Question

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

我想出的解决方案正确解决了网站建议的所有 public 个测试用例的问题，但它无法解决一个或多个隐藏的私人测试用例。

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

            #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 的评论修改了代码，程序现在不会像以前对隐藏的私人测试用例那样超过时间限制，但现在得到一个判决 "Wrong answer"（仅适用于私有测试用例）。我会尝试找出算法错误可能是什么。感谢所有回答的人。

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。（即使两个对象具有相同的 time 和相同的 type(EventType::LEAVE)，它也返回 true，而当两个对象相同时，它应该返回 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;
    }
}

Answer 2

您可以通过完全取消 Event class 并使用 pair<int,int> 来简化您的代码。配对按第一个元素（即您的活动时间）排序，然后按第二个元素排序。我建议使用类似于以下的代码填充您的矢量：

    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());

如您所见，排序不需要定义任何额外的内容。它只是工作 (tm)。

两个陷阱：

如果我在 t0 到达，而其他人在 t0 离开，则聚会人数没有改变。
如果很多人同时到达或离开，你应该只重新计算一次帮助变化（如果是0，完全忽略它，就像前面的陷阱）。

我也可以确认，对于这个特定的问题，法官不会接受任何使用复杂结构的答案（我最初尝试用 map<int, int> 来解决它）。单纯表演

    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
    }

让你超过时间限制（即使它会自动排序）。因此，即使区间树非常适合重复的区间查询，它们也不是解决这个特定问题（只查询一次）的正确工具。

祝你为那个难以捉摸的 AC 修复代码好运！我可以确认它是可以实现的。

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

Duration of maximum number of overlapping events

c++

algorithm

sorting

overlap