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