Объединение временных интервалов на php...
есть пара временных массивов в виде:
(
[0] => Array
(
[from] => 1097562600
[to] => 1097577000
)
[1] => Array
(
[from] => 1097578800
[to] => 1097582400
)
[2] => Array
(
[from] => 1097583000
[to] => 1097586300
)
)
Array
(
[0] => Array
(
[from] => 1097562501
[to] => 1097577000
)
[1] => Array
(
[from] => 1097578800
[to] => 1097582400
)
[2] => Array
(
[from] => 1097583000
[to] => 1097586300
)
)
from - время начала интервала
to - время конца интервала
Требуется выполнить простейшую оперцию из теории множеств - объединение!
Т.е. получить результирующий массив отрезков, которые бы внутри себя содержали все отрезки из обоих массивов...
Кто-нибудь сталкивался с подобной задачей? Каков примерный алгоритм решения?
Если брать решение в лоб, то получается так:
-взять первый отрезок первого массива
-проверить не накладывается ли на него какой-нибудь отрезок из 2-го массива
-если накладывается(и выходит за границы), то первый элемент результирующего массива будет объединять эти отрезки
- проверить, остались ли отрезки первого массивы, вне границ первого результирующего отрезка
- если остались, то взять этот первый элемент и аналогично сравнить его со всеми элементами 2-го массива, которые выходят за его границы....
Каждый из этих пунктов - это уже объемный кусок кода. Может даже реккурсию придется применять....
Интересно, есть какие-нибудь более простые варианты решения данной задачи....
from - время начала интервала
to - время конца интервала
Требуется выполнить простейшую оперцию из теории множеств - объединение!
Т.е. получить результирующий массив отрезков, которые бы внутри себя содержали все отрезки из обоих массивов...
Кто-нибудь сталкивался с подобной задачей? Каков примерный алгоритм решения?
Если брать решение в лоб, то получается так:
-взять первый отрезок первого массива
-проверить не накладывается ли на него какой-нибудь отрезок из 2-го массива
-если накладывается(и выходит за границы), то первый элемент результирующего массива будет объединять эти отрезки
- проверить, остались ли отрезки первого массивы, вне границ первого результирующего отрезка
- если остались, то взять этот первый элемент и аналогично сравнить его со всеми элементами 2-го массива, которые выходят за его границы....
Каждый из этих пунктов - это уже объемный кусок кода. Может даже реккурсию придется применять....
Интересно, есть какие-нибудь более простые варианты решения данной задачи....
Нууу..., я не решал такой задачи, но могу предложить следующий вариант.
1. Объединить оба массива, не важно как, чтобы один просто получился.
2. Отсортировать его по "from", т.е. from каждого последующего элемента должен быть больше или равен from предыдущего элемента.
[Далее сам процесс объединения]
3. i = 0; если i>sizeof(array)-2 то (9), иначе (4)
4. если array[to] > array[i+1][from] то (5) иначе (8)
5. если array[to] < array[i+1][to] то array[to] = array[i+1][to]
6. тут нужно убрать из массива элемент [i+1], сместив все элементы [i+2]..[sizeof(array)-1]. (думаю удобней всего это через array_splice сделать)
7. здесь цикл завершается, идем опять на (3)
8. i++ и тоже на (3)
9. Выход
Ну и все..., возможно где-то есть ошибки, но вообще работать должно...