Fusion de plages en C ++

Question

J'ai une liste de façon aléatoire commandé unique fermé plages de R₀...R_n-1 où

R_i = [r1_i, r2_i] (r1_i <= r2_i)

Par la suite certains des plages de chevauchement (partiellement ou totalement), et donc nécessiterait de fusion.

Ma question est, quels sont les best-of-breed les algorithmes ou les techniques utilisées pour la fusion de ces plages. Des exemples de tels algorithmes ou des liens vers des bibliothèques effectuer une telle opération de fusion serait génial.

Answer 1

Ce que vous devez faire, c'est:

1. Trier les éléments lexicographiquement où la clé de plage est [r_start, r_end]

2. Itérer la liste triée et vérifier si l'élément actuel chevauche le suivant. S'il étend l'élément actuel à r [i] .start, r [i + 1] .end et à l'élément suivant. S'il ne se chevauche pas, ajoutez le courant à la liste de résultats et passez à l'élément suivant.

Voici un exemple de code:

     vector<pair<int, int> > ranges;
    vector<pair<int, int> > result;
    sort(ranges.begin(),ranges.end());
    vector<pair<int, int> >::iterator it = ranges.begin();
    pair<int,int> current = *(it)++;
    while (it != ranges.end()){
       if (current.second > it->first){ // you might want to change it to >=
           current.second = std::max(current.second, it->second); 
       } else {
           result.push_back(current);
           current = *(it);
       }
       it++;
    }
    result.push_back(current);
 

Answer 2

Coup de pouce.Icl pourraient être utiles pour vous.

La bibliothèque propose quelques modèles que vous pouvez utiliser dans votre situation:

• interval_set - met en œuvre un jeu comme une série d'intervalles de fusion attenant à intervalles réguliers.
• separate_interval_set - met en place la définir comme un ensemble d'intervalles de quitter attenant à intervalles distincts
• split_interval_set - met en place la définir comme un ensemble d'intervalles sur l'insertion de chevauchement des intervalles de split

Il est un exemple pour la fusion des intervalles de la bibliothèque :

interval<Time>::type night_and_day(Time(monday,   20,00), Time(tuesday,  20,00));
interval<Time>::type day_and_night(Time(tuesday,   7,00), Time(wednesday, 7,00));
interval<Time>::type  next_morning(Time(wednesday, 7,00), Time(wednesday,10,00));
interval<Time>::type  next_evening(Time(wednesday,18,00), Time(wednesday,21,00));

// An interval set of type interval_set joins intervals that that overlap or touch each other.
interval_set<Time> joinedTimes;
joinedTimes.insert(night_and_day);
joinedTimes.insert(day_and_night); //overlapping in 'day' [07:00, 20.00)
joinedTimes.insert(next_morning);  //touching
joinedTimes.insert(next_evening);  //disjoint

cout << "Joined times  :" << joinedTimes << endl;

et la sortie de cet algorithme:

Joined times  :[mon:20:00,wed:10:00)[wed:18:00,wed:21:00)

Et ici, à propos de la complexité des algorithmes:

Le temps de la Complexité de Plus

Answer 3

Un algorithme simple serait:

• Trier les plages par valeurs de départ
• Itérer sur les plages du début à la fin, et chaque fois que vous trouvez une plage qui chevauche la suivante, fusionnez-les

Answer 4

O (n * log (n) +2n):

• Faites un mappage de r1_i -> r2_i ,
• QuickSort sur les r1_i ,
• parcourir la liste pour sélectionner pour chaque r1_i -value la plus grande r2_i -value,
• avec cette valeur r2_i vous pouvez ignorer tous les r1_i qui sont plus petits que r2_i

Answer 5

La réponse de jethro contient une erreur. Ça devrait être

 if (current.second > it->first){
    current.second = std::max(current.second, it->second);        
} else {