अतिव्यापी घटनाओं की अधिकतम संख्या की अवधि

Question

मेरे एल्गोरिदमिक कौशल में सुधार करने की कोशिश करते समय मुझे खुद को निम्नलिखित समस्या में फंस गया है जो संक्षेप में आपको उस समय की अवधि खोजने के लिए कहता है जहां कमरे में अधिकतम संख्या में लोग मौजूद हैं :

https://jutge.org/problems/P27158_en

समाधान मैं इस समस्या को सही ढंग से सभी सार्वजनिक परीक्षण मामलों वेबसाइट द्वारा सुझाए गए के लिए हल के साथ आए हैं, लेकिन यह एक या अधिक छिपा निजी परीक्षण मामलों के लिए विफल रहता है।

मेरा समाधान प्रत्येक ईवेंट के लिए std :: वेक्टर में दो प्रविष्टियों को बचाता है: एक आगमन के लिए और एक छोड़ने के लिए, प्रत्येक में [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

मैं इस की तुलना समारोह बदल गया है और टीएलई दूर चला गया (और एक वाशिंगटन के लिए बदल):

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 था), जबकि यह गलत वापस आ गए चाहिए जब दोनों वस्तुओं के बराबर हैं।)

संपादित करें:

आप हो रही है वाशिंगटन क्योंकि इस तरह के परीक्षण मामलों के:

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

आप देख सकते हैं, छंटाई कुछ भी अतिरिक्त परिभाषित करने की आवश्यकता नहीं है। यह सिर्फ काम करता है (टीएम)।

दो नुकसान:

• अगर मैं 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 
    } 

आपको समय-सीमा-पार हो जाता है (भले ही यह स्वचालित रूप से स्वचालित हो)। तो यदि अंतराल के पेड़ बार-बार अंतराल प्रश्नों के लिए बहुत अच्छे हैं, तो वे इस विशेष समस्या के लिए सही उपकरण नहीं हैं (जो केवल एक बार पूछताछ करते हैं)।

उस भाग्यशाली एसी के लिए अपने कोड को ठीक करने के लिए शुभकामनाएं! मैं पुष्टि कर सकता हूं कि यह प्राप्य है।