Отсортируйте точки начала и конца всех отрезков вместе, помеченные с +1 или с -1 в зависимости от стороны.
Далее есть вот у вас все точки на числовой прямой. Пройдитесь по ним слева направо считая, сколько сейчас открыто отрезков. Если между двумя точками отркрыто 0 отрезков - добавляйте отрезок в ответ.
Удобный трюк - сдвинуть начала отрезков на 1 влево, чтобы отрезок, вырезающий число 1 (1..1) был длиной 1.
Представьте, что у вас на числовой прямой 10000 единичных кусочков, с 0 до 10000 - это ваши изначальные числа. Если вы хотите вырезать отрезок 5..7 (числа 5, 6 и 7), то вам надо на этой прямой вырезать отрезок [4...7] - от точки 4 до точки 7.
Плюс добавьте точки начала и конца, чтобы отдельно их не обрабатывать и тогда вам надо выдать все отрезки покрытые ровно одним вырезаемым отрезком и не надо оотдельно разбирать случай самого левого и самого правого кусоков в ответе.
php не знаю, вот вам на C++. Спрашивайте, если что непонятно:
vector<pair<int, int>> CutOutSegments(int begin, int end, vector<pair<int, int>> segments)
// Массив из пар чисел. Пустой массив, в который будем добавлять строки из 2 чисел.
vector<pair<int, int>> events;
events.push_back({begin-1, 1}); // добавляем строку с числами begin и 1.
events.push_back({end, -1});
for (auto s: segments) {
events.push_back({s.first-1, 1}); // s.first - начало отрезка.
events.push_back({s.second, -1}); // s.second - конец отрезка.
}
sort(events.begin(), events.end());
int prev_pos = events[0].first;
int count = 0;
vector<pair<int, int>> result;
for (auto e: events) { // e - строка массива events. e.first/second - 2 числа в ней.
if (prev_pos < e.first && count == 1) {
result.push_back(prev_pos + 1, e.first); // добавялем +1, что бы отрезок [0, 1] был выдан как одно число 1..1.
}
count += e.second;
if (e.first == end) break;
}
return result;
}
Возмождно последний цикл можно переписать через reduce, но вряд ли будет короче или читабельнее.
