重叠事件的最大次数的持续时间
在努力提高我的算法技巧的同时，我发现自己陷入了下面的问题，总之，要求你找出房间中存在最多人数的时间段的持续时间：
https://jutge.org/problems/P27158_en
我提出的解决方案正确地解决了网站建议的所有公共测试用例的问题，但是它对一个或多个隐藏的私人测试用例无效。
我的解决方案为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的评论对代码进行了相应的修改，并且程序现在没有像以前那样对隐藏的私人测试用例进行时间限制，但是现在得到了“错误答案”（仅针对私人测试用例）的判决。 我会试着找出算法错误可能是什么。 感谢所有回答的人。
我改变了比较功能，并且TLE消失了（并且改变为WA）：
bool operator< ( const Event& e ) const
{
return (time < e.time) || (time == e.time && type==EventType::LEAVE && e.type != EventType::LEAVE);
}
正如评论中所建议的那样，这样做的原因是您给出的比较函数没有严格的弱排序。 （它返回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;
}
}
通过彻底取消Event类，并使用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）。
两个陷阱：
我也可以证实，对于这个特定的问题，法官不会接受任何使用复杂结构的答案（我最初试图用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代码！ 我可以证实它是可以实现的。
链接地址: http://www.djcxy.com/p/32505.html