3. Überlappende Intervalle

Überlappende Intervalle

  • ?

    Guten Abend,

    ich habe eine Frage, wie man ein Problem algorithmisch elegant in C++ lösen könnte.

    Ich habe N Intervalle, die alle einen Start und Endwert sowie Namen haben (Anfangs immer nur einen), also sowas:

    struct Interval {
    double start, end;
    vector<string> names;
};

    Sagen wir ich habe beispielweise diese 3 Intervalle:

    Interval A(0, 100, "A"); // Intervall A geht von 0 bis 100
Interval B(80, 200, "B");
Interval A(150, 300, "C");

    Ich will nun alle Intervalle so vereinigen, dass ich in jedem neuen Intervall weiß, welche Intervalle aktiv sind.
    Das Ergebnis aus den oberen 3 Intervallen wäre hier:
    1. Interval: (0, 80, "A") // Von 0 bis 80 gibt es nur Intervall A
    2. Interval: (80, 100, "A", "B") // Von 80 bis 100 ist Intervall A und B (überlappen sich)
    3. Interval: (100, 150, "B")
    4. Interval: (150, 200, "B", "C")
    5. Interval: (200, 300, "C")

    Wie könnte man das schön lösen? Gibts da evtl. was in std::algorithm oder boost?

    0
  • ?

    Du machst eine Liste von "Events" (um 0 füge "A" ein; um 100 entferne "A"; um 80 füge "B" ein, etc.) und sortierst diese nach der Zeit. In einem set merkst du dir, welche Intervalle aktiv sind. Dann gehst du durch alle Events und updatest das set. Wenn du bei jeder Änderung der Zeit eine Kopie des Sets speicherst, hast du dein Endresultat.

    0
  • W

    zweizeiler schrieb:

    Du machst eine Liste von "Events" (um 0 füge "A" ein; um 100 entferne "A"; um 80 füge "B" ein, etc.) und sortierst diese nach der Zeit. In einem set merkst du dir, welche Intervalle aktiv sind. Dann gehst du durch alle Events und updatest das set. Wenn du bei jeder Änderung der Zeit eine Kopie des Sets speicherst, hast du dein Endresultat.

    Gute Idee,

    ich setze das mal um:

    #include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
#include <string>
#include <set>
#include <functional>
#include <tuple>

struct Interval 
{
    template< typename C >
    Interval( double s, double e, const C& c )
        : start(s)
        , end_(e)
        , names( begin(c), end(c) )
    {}
    Interval( double s, double e, std::string&& name )
        : start(s)
        , end_(e)
        , names( 1, name )
    {}
    template< typename E, typename Traits > friend
        std::basic_ostream< E, Traits >& operator<<( std::basic_ostream< E, Traits >& out, const Interval& i )
    {
        out << "[" << i.start << ".." << i.end_ << "] ";
        copy( begin(i.names), end(i.names), std::ostream_iterator< std::string >( out, " " ) );
        return out;
    }
    double start, end_;
    std::vector< std::string > names;
};

using Event = std::tuple< double, std::function< void( std::set< std::string >& ) > >;

Event begin( const Interval& i )
{
    return std::make_pair( i.start, 
        [i]( std::set< std::string >& s ) {  s.insert( i.names.front() ); } );
}
Event end( const Interval& i )
{
    return std::make_pair( i.end_, 
        [i]( std::set< std::string >& s ) { s.erase( i.names.front() ); } );
}

int main()
{
    using namespace std;
    vector< Interval > intervalle = {
        Interval( 0., 100., std::string("A") ),
        Interval( 80., 200., std::string("B") ),
        Interval( 150., 300., std::string("C") )
    };
    vector< Event > events;   // .. eine Liste von "Events" ..
    for( auto i: intervalle )
    {
        events.push_back( begin(i) );   // um 0 füge "A" ein; 
        events.push_back( end(i) );     // um 100 entferne "A";
    }
    // .. und sortierst diese nach der Zeit ..
    sort( begin(events), end(events), []( const Event& e1, const Event& e2 )->bool { return get<0>(e1) < get<0>(e2); } );

    if( !events.empty() )
    {
        set< string > buffer;   // In einem set merkst du dir, welche Intervalle aktiv sind.
        auto prev = begin(events);
        for( auto next = prev; ++next != end(events); prev = next ) // Dann gehst du durch alle Events ..
        {
            get<1>(*prev)( buffer ); // .. und updatest das set. Wenn du bei jeder Änderung der Zeit ..
            cout << Interval( get<0>(*prev), get<0>(*next), buffer ) << endl; // .. eine Kopie speicherst, hast du dein Endresultat
        }
    }
    return 0;
}

    Gruß
    Werner

    0
  • ?

    Werner Salomon schrieb:

    Gute Idee, ich setze das mal um:

    Wow, das ist wirklich sehr wortgetreu umgesetzt. Das einzige, was fehlt, ist

    Wenn du bei jeder Änderung der Zeit ..

    Füge in intervalle noch " Interval( 0., 80., std::string("D") ), Interval( 0., 80., std::string("E") ), " ein und man erhält so Stellen wie "[0..0] A\n[0..0] A D" und "[80..80] A B D E\n[80..80] A B E", was vermutlich unerwünscht ist.

    0
  • ?

    algor schrieb:

    Wie könnte man das schön lösen? Gibts da evtl. was in std::algorithm oder boost?

    #include <iostream>
#include <set>
#include <string>
#include <utility>

#include <boost/icl/interval_map.hpp>

int main(){
  using namespace std;
  using namespace boost::icl;

  using names = set<string>;

  interval_map<int, names> m;
  m+=make_pair(interval<int>::right_open(0,100), names{"A"});
  m+=make_pair(interval<int>::right_open(80,200), names{"B"});
  m+=make_pair(interval<int>::right_open(150,300), names{"C"});

  for(const auto& it : m)
    cout << it.first << " : " << it.second << '\n';
}
/*
[0,80) : {A }
[80,100) : {A B }
[100,150) : {B }
[150,200) : {B C }
[200,300) : {C }
*/

    Boost.Icl kannte ich auch nicht.
    Schadet aber sicher nicht, die Bibliothek hier mal zu erwähnen.

    0
Anmelden zum Antworten