比较对象数组元素的最佳方法

Question

所以我有一个数组，其中包含一些同时具有 StartTime 和 Duration 成员变量的对象。 startTime 变量是格式为“14:20”的字符串，而 Duration 变量是一个数字，表示分钟数。

你们能推荐遍历数组和组合重叠元素的最佳逻辑吗？例如，如果数组有两个对象，第一个对象的开始时间为“00:00”，持续时间为 60，第二个对象的开始时间为“08:00”，持续时间为 120，它们将分开元素但是，如果第二个对象的开始时间为“00:30”，持续时间为 120，则这两个对象将合并为一个对象，开始时间为“00:00”，持续时间为 150。

一段时间以来，我一直坚持这个的一般逻辑，因为我不知道如何处理两个块合并时的情况，但是新的合并块创建了一个必须处理的新重叠。我只是在想这个错误吗？通常我对这类事情很在行，但在这里却很挣扎。

Answer 1

在@gavgrif 上扩展...

我推荐一些类似的东西。

创建新数组字段 ['start'] 从午夜开始的分钟数 (14:20 -> 188)
按'start'字段对数组排序
遍历数组以查找重叠项以合并到段中。其中重叠是这个新项目的开始不大于段结束。

php 示例：

$segment  = array('start' => -1, 'end' => -1);  // force new segment on init
$segments = array();
foreach ($items as $item) {
    if ($item['start'] > $segment['end']) {

        // add current segment (ignore initial fake segment) to segments
        if ($segment['start'] > -1) {
            // close out current segment
            $segments[] = $segment;                
        }

        // start new segment
        $segment = $item;

    } else {

        // increment segment end if its later than current segment end
        $segment['end'] = max($segment['end'], $item['end'];
    }        
}

// close out final segment
$segments[] = $segment;

Answer 2

我将通过创建两棵树来做到这一点，一棵由 StartTime 索引，另一棵由 EndTime (StartTime + Duration) 索引。在两棵树中搜索重叠的元素。搜索完成后，将从两棵树中删除所有找到的元素，并将单个新元素（StartTime = minStartTime（searchResult），EndTime = maxEndTime（searchResult））插入两棵树中。

使用了一些额外的存储空间，但我相信这会使您的重叠问题变得微不足道。

（树的实现留作练习:)

比较对象数组元素的最佳方法

Best way to compare the elements of an array of objects

javascript

arrays

logic