日历数据排序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个额外的属性，sum和col（列）。 Sum是组成组的列（每个组）的总和，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
}   
]

因此，因为项目ID：3来自id：1和id：2之间和之间，请注意这三个项目的sum属性是2，而id：3的col是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 }

我认为我理解的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>');