алгоритм — лучший способ построить данные временной шкалы из наборов начальной и конечной отметок времени

Question

алгоритм — лучший способ построить данные временной шкалы из наборов начальной и конечной отметок времени

У меня есть ряд элементов массива, который выглядит следующим образом:

[{
"id": 1,
"start": "2017-04-05 16:27:08",
"end": "2017-04-05 16:30:45"}, {
"id": 2,
"start": "2017-04-05 16:15:08",
"end": "2017-04-05 16:22:45"}, {
"id": 2,
"start": "2017-04-05 16:10:08",
"end": "2017-04-05 16:17:45"}]

Я хотел бы построить массив из этого массива, который позволит мне отображать временную шкалу моих элементов. Временная шкала всегда будет иметь одну линию на оси Y. Если есть несколько элементов, которые перекрывают друг друга в исходном массиве, эти несколько элементов будут объединены в один элемент.

Для приведенного выше массива результирующий массив, который я ищу, будет выглядеть так:

[{
"start": "2017-04-05 16:10:08",
"end": "2017-04-05 16:22:45"}, {
"start": "2017-04-05 16:27:08",
"end": "2017-04-05 16:30:45"}]

Какой лучший способ сделать это?

0

algorithm php sorting

Решение

Другие решения

Здесь мы используем простой foreach петля, для достижения желаемого результата. дополнительно мы проверяем timestamp и сравнивая их

Попробуйте этот фрагмент кода здесь

<?php
ini_set('display_errors', 1);
$json='[{
"id": 1,
"start": "2017-04-05 16:27:08",
"end": "2017-04-05 16:30:45"}, {
"id": 2,
"start": "2017-04-05 16:15:08",
"end": "2017-04-05 16:22:45"}, {
"id": 2,
"start": "2017-04-05 16:10:08",
"end": "2017-04-05 16:17:45"}]';
$array=  json_decode($json,true);
$result=array();
foreach($array as $key => $value)
{
if(isset($result[$value["id"]]))
{
//checking which start-time is less
if(strtotime($result[$value["id"]]["start"]) > strtotime($value["start"]))
{
$result[$value["id"]]["start"]=$value["start"];
}
//checking which end-time is greater
if(strtotime($result[$value["id"]]["end"]) < strtotime($value["end"]))
{
$result[$value["id"]]["start"]=$value["end"];
}
}
else
{
$id=$value["id"];
unset($value["id"]);
$result[$id]=$value;
}
}
print_r($result);

Выход:

Array
(
[1] => Array
(
[start] => 2017-04-05 16:27:08
[end] => 2017-04-05 16:30:45
)

[2] => Array
(
[start] => 2017-04-05 16:10:08
[end] => 2017-04-05 16:22:45
)

)

0

Источник

Accepted Answer

Это очень сложно. Если в нем небольшое количество элементов, тогда будет достаточно манипулировать данными в PHP или Javascript, но если в нем будет большое количество элементов, то это может быть сделано в базе данных.

Что касается небольшого количества предметов — вам просто нужно

сортировать по началу
перебирать массив и для каждого элемента
- переберите более поздние записи в массиве, чтобы увидеть, пересекаются ли они — и объединяют ли они их

Это имеет порядок O (n ^ 2), который плохо масштабируется.

Выполнение этого в базе данных с обычным индексом мало чем поможет — это отлично подходит для запросов, фильтруемых (например,)

SELECT *
FROM table t
WHERE t.value BETWEEN $a_literal AND $another_literal

Но такие показатели не работают для

SELECT *
FROM table t
WHERE $a_literal BETWEEN t.start and t.end

если диапазоны, определенные в каждой записи, не намного меньше, чем общий диапазон данных, хранящихся в таблице.

На этом этапе решение состоит в том, чтобы использовать геопространственную индексацию и отображать ваши временные интервалы в области в двумерном пространстве (поскольку MySQL не поддерживает одномерную геопространственную индексацию).

Следовательно, полное решение этой проблемы может быть реализовано с порядком O (nlog (n)), но я достаточно подробно рассказал об этом здесь.

СУБД хороши в быстрой обработке массовых операций — поэтому описанный первоначально метод грубой силы будет работать быстрее в базе данных, чем в PHP / Javascript, — но вычислительный ресурс легче масштабировать в PHP и в Javascript.

1