重疊事件的最大次數

Question

在試圖提高我的算術技巧時，我發現自己陷入了下面的問題，總之，要求您找出房間中存在最多人數的時間段的持續時間：

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相應地修改代碼註釋和程序現在，因爲它的隱藏私人測試用例以前那樣不超過時間限制，但現在得到一個判決「錯誤的答案」（僅適用於私人測試用例）。我會試着找出算法錯誤可能是什麼。感謝所有回答的人。

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

Answer 2

您可以通過脫離了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）。

兩個陷阱：

• 如果我到達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代碼！我可以確認它是可以達到。