queues - merge sort algoritmo c++

Fusionando Rangos En C++

Question

Tengo una lista de rangos de final cerrado únicos aleatorios ordenados R ₀ ... R _n-1 donde

R _i = [r1 _i , r2 _i ] (r1 _i <= r2 _i )

Posteriormente, algunos de los rangos se superponen (parcial o totalmente) y, por lo tanto, requieren fusión.

Mi pregunta es, ¿cuáles son los mejores algoritmos o técnicas utilizadas para fusionar dichos rangos? Los ejemplos de tales algoritmos o enlaces a bibliotecas que realizan tal operación de fusión serían excelentes.

Answer 1

La respuesta de jetro contiene un error. Debería ser

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

Answer 2

Lo que debes hacer es:

1. Ordene los artículos lexicográficamente donde la clave de rango es [r_start, r_end]

2. Iterar la lista ordenada y comprobar si el elemento actual se superpone con el siguiente. Si extiende el elemento actual para que sea r [i] .start, r [i + 1] .end, y pase al siguiente elemento. Si no se superponen, agregue el actual a la lista de resultados y pase al siguiente elemento.

Aquí hay un código de muestra:

    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 3

Mi algoritmo no usa espacio extra y también es liviano. He utilizado el enfoque de 2-pointer . ''i'' sigue aumentando mientras que ''j'' hace un seguimiento del elemento actual que se está actualizando. Aquí está mi código:

bool cmp(Interval a,Interval b)
 {
     return a.start<=b.start;
 }
vector<Interval> Solution::insert(vector<Interval> &intervals, Interval newInterval) {
    int i,j;
    sort(intervals.begin(),intervals.end(),cmp);
    i=1,j=0;
    while(i<intervals.size())
    {
        if(intervals[j].end>=intervals[i].start)  //if overlaps
        {
            intervals[j].end=max(intervals[i].end,intervals[j].end); //change
        }
        else
        {
            j++;
            intervals[j]=intervals[i];  //update it on the same list
        }
        i++;
    }
    intervals.erase(intervals.begin()+j+1,intervals.end());
    return intervals;
}

El intervalo puede ser una clase o estructura pública con miembros de datos ''inicio'' y ''final''. Feliz codificación :)

Answer 4

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

• Haz un mapeo de r1_i -> r2_i ,
• QuickSort sobre el r1_i ''s,
• r1_i la lista para seleccionar para cada valor r1_i valor más grande de r2_i ,
• con ese valor de r2_i puede omitir todos los r1_i subsiguientes que sean más pequeños que r2_i

Answer 5

Un algoritmo simple sería:

• Ordenar los rangos por valores iniciales
• Iterar sobre los rangos de principio a fin, y cada vez que encuentre un rango que se superponga con el siguiente, combínelos

Answer 6

Boost.Icl puede ser de utilidad para usted.

La biblioteca ofrece algunas plantillas que puede usar en su situación:

• interval_set: implementa un conjunto como un conjunto de intervalos, combinando intervalos adyacentes.
• separate_interval_set: implementa un conjunto como un conjunto de intervalos, dejando separados los intervalos adyacentes
• split_interval_set - implementa un conjunto como un conjunto de intervalos - en la inserción los intervalos superpuestos se dividen

Hay un example para combinar intervalos con la biblioteca:

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;

y la salida de este algoritmo:

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

Y aquí sobre la complejidad de sus algoritmos:

Complejidad del tiempo de la adición