Имеется n-промежутков, вида: [a1,b1];[a2,b2];...;[an,bn]. Необходимо получить объединение данной последовательности промежутков. Например:
на входе: [1,2];[2,3];[3,4] тогда на выходе: [1,4]
на входе: [1,2];[2,3];[3,4];[5,6];[6;7] тогда на выходе: [1,4];[5,7]
и так далее
Я решила эту задачу простым циклом с проверкой всех возможных вариантов объединение промежутков. Но! Я не совсем уверена в корректности, вдруг найдется такой промежуток, для которого алгоритм выдаст неправильный результат.
struct Interval{
double a, b;
Interval(){}
Interval(double A, double B){a = A; b = B;}
};
vector<Interval> H;
for(int k = 0; k < X.size(); ++k){
double a = X[k].a;
double b = X[k].b;
if(b-a < eps) continue;
for(int i = k; i < X.size()-1; ++i){
if(fabs(X[i].b-X[i+1].a) < eps){
b = X[i+1].b;
k = i+1;
continue;
}
else break;
}
H.push_back(Interval(a, b));
}
У меня появилась идея рекурсивного алгоритма: рассматриваются два соседних промежутка, если I[i].b == I[i+1].a, то объединить два промежутка в один и получить [I[i].a, I[i+1].b]. Но, к сожалению, все мои реализации выдают неверный ответ. Буду рада, если предложите какие-то идеи по решению данной задачи.