Календарь сортировки данных JSon дерево

Question

мне нужна помощь в следующем, Вот некоторые данные JSON

[ 
{ 
    "id" : 1, 
    "from" : 10, 
    "to" : 11 
}, 
{ 
    "id" : 2, 
    "from" : 11, 
    "to" : 12 
}, 
{ 
    "id" : 3, 
    "from" : 10.5, 
    "to" : 11.5 
}, 
{ 
    "id" : 4, 
    "from" : 9, 
    "to" : 9.5 
} 
] 

Я пытаюсь подготовить данные, как это я могу отобразить его на экране, так что каждый объект будет содержать 2 дополнительных свойства, сумма и столбец (столбец). Сумма представляет собой сумму столбцов (per say), составляющих группу, а col - в столбце, в котором находится объект. Это пример данных. Поэтому я ищу рекурсивный способ перемещения данных, чтобы установить эти два дополнительных свойства. Данные должны выглядеть следующим образом:

[ 
{ 
    "id" : 1, 
    "from" : 10, 
    "to" : 11, 
    "sum" : 2, 
    "col" : 1 
}, 
{ 
    "id" : 2, 
    "from" : 11, 
    "to" : 12, 
    "sum" : 2, 
    "col" : 1 
}, 
{ 
    "id" : 3, 
    "from" : 10.5, 
    "to" : 11.5, 
    "sum" : 2, 
    "col" : 2 
}, 
{ 
    "id" : 4, 
    "from" : 9, 
    "to" : 9.5, 
    "sum" : 1, 
    "col" : 1 
} 
] 

Так потому Item ID: 3 из между идентификатором: 1 и ид: 2 от и до, обратите внимание свойство суммы этих трех элементов является 2 и что цв из id: 3 равно 2. Я предполагаю, что это простая версия данных. Дополнительное гнездование может существовать там, где, например, дополнительная сумма объекта может равняться 3 и col равна 3.

Я не уверен, какая структура данных это напоминает? Какое-то дерево. Как я могу пройти эти пункты (думая рекурсивно) и установить эти дополнительные свойства с наименьшей временной сложностью? Возможно, у меня есть сортировка первой.

Любое направление или помощь были бы высоко оценены!

Answer 1

Подход.

Пока я правильно понимаю, вам нужно назначить два свойства каждому элементу массива. pos - это столбец расписания в виде списка. Когда есть два или более совпадающих назначения, позиция 1 для первой встречи, позиция 2 для второго назначения и т. Д.

  pos = 1       pos = 2 
---------------------------  ------------------------------- 
{ id: 1, from: 10, to: 11 }  { id: 3, from: 10.5, to: 11.5 } 
{ id: 2, from: 11, to: 12 } 
{ id: 4, from: 12, to: 13 } 

The sum является то, что я думаю, я понял, счетчик одновременных назначений.

Для первой части решение использует вспомогательную переменную schedule. Эта переменная имитирует таблицу с назначением. В каждом массиве все встречи не перекрываются. Размер массива соответствует желаемому pos.

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

Алгоритм нуждается в сортировке данных.

Первый массив в результате - это расписание.
Второй - это оригинальный массив, отсортированный и добавленный с требуемыми свойствами pos и sum.

var data = [ 
 
     { id: 1, from: 10, to: 11 }, 
 
     { id: 3, from: 10.5, to: 11.5 }, 
 
     { id: 2, from: 11, to: 12 }, 
 
     { id: 4, from: 12, to: 13 }, 
 
    ], 
 
    schedule = []; 
 

 
data.sort(function (a, b) { return a.from - b.from || a.to - b.to; }); 
 

 
data.forEach(function (a, i) { 
 
    schedule.some(function (b, j) { 
 
     if (b.length && b[b.length - 1].to <= a.from) { 
 
      b.push(a); 
 
      return true; 
 
     } 
 
    }) || schedule.push([a]); 
 
}); 
 

 
schedule.forEach(function (a, i) { 
 
    a.forEach(function (b) { 
 
     b.pos = i + 1; 
 
    }); 
 
}) 
 

 
data.forEach(function (a, i, aa) { 
 
    var j, sum = 1; 
 
    while (i + sum < data.length && data[i + sum].from < a.to && a.to <= data[i + sum].to) { 
 
     sum++; 
 
    } 
 
    for (j = i; j < i + sum; j++) { 
 
     if (!(aa[j].sum >= sum)) { 
 
      aa[j].sum = sum; 
 
     } 
 
    } 
 
}); 
 

 
document.write('<pre>' + JSON.stringify(schedule, 0, 4) + '</pre>'); 
 
document.write('<pre>' + JSON.stringify(data, 0, 4) + '</pre>');