合并时隙的最简单算法

Question

下图试图表示时隙列表。最后一行代表合并结果。每个槽由 start/end（日期和时间）和类型 (green/yellow) 组成。最终的结果需要return一些规则的合并插槽，其中如果有绿色与黄色重叠，则绿色为准。

我目前的方法是从按时间排序的列表开始。但此刻我的代码变得混乱，不知何故使用递归逻辑....我不确定这是否是最简单的方法。

如果“时隙”的大小在某种程度上是独一无二的，那将很容易，但情况并非如此，因为我正在处理 minutes/seconds...并且“重叠”可以与如此小的时间段相吻合单位。

我不是要解决方案代码，而是要一些帮助，指出一些用于此类问题的已知算法。我可以阅读的一些网页网址等。谢谢。

Answer 1

如果您使用排序列表，解决方案非常简单。

在开始时间和结束时间中拆分每个间隔，每个间隔带有 +1 和 -1 标签。如果您需要根据颜色实现额外的逻辑，请将该信息集成到标签中。

现在对所有时间进行递增排序（如果列表最初已排序，则使用完整排序或合并）。通过增加处理时间，您将保持正在进行的任务数。他们的联合对应于一个非零数。您可以根据“彩色”数字实施您想要的任何规则。

Answer 2

我想我找到了一个乍看起来很简单的解决方案。我仍然需要用其他一些样本对其进行测试...但我相信如果仍然存在任何错误，解决方案不会增加其复杂性。

无论如何，请随时帮助我改进它。谢谢

/***************************************************************************/
var processDateTime = filter.From;
var continueLoop = true;                    
while (continueLoop)
{
    var target = mergedMachineSlotsOfTimeRaw.Where(x => x.From >= processDateTime)
                                            .OrderBy(x => x.From).FirstOrDefault();
    if (target == null)
    {
        continueLoop = false;
    }
    else
    {
        mergedMachineSlotsOfTimeRaw = GetMergedSlot(target, mergedMachineSlotsOfTimeRaw);
        processDateTime = target.To.Value;
    }
}                                                                
/***************************************************************************/

其他功能

private List<DTOTempMachineSlot> GetMergedSlot(DTOTempMachineSlot original,
                                       List<DTOTempMachineSlot> originalList)
{
    var overlappedEntries = originalList.Where(x => x.Id != original.Id
                                                    && x.From >= original.From
                                                    && x.From < original.To);
    if (overlappedEntries.Count() == 0)
    {
        return originalList;
    }
    var newFinalList = new List<DTOTempMachineSlot>();
    var longestEntry = overlappedEntries.OrderByDescending(x => x.To).FirstOrDefault();

    var deleteLongestEntry = false;
    if (original.State == longestEntry.State)
    {
        if(original.To < longestEntry.To) {
                  original.To = longestEntry.To;
        }
        deleteLongestEntry = true;
    }
    else if (original.State == "S" && longestEntry.State == "E")
    {
        original.To = original.To;
        longestEntry.From = original.To.Value;
    }
    else if (original.State == "E" && longestEntry.State == "S")
    {
        original.To = longestEntry.To;
    }

    newFinalList.Add(original);
    if (deleteLongestEntry == false)
    {
        newFinalList.Add(longestEntry);
    }
    newFinalList.AddRange(originalList.Where(x => x.Id != original.Id 
                    && overlappedEntries.Any(y=>y.Id == x.Id) == false));

    return newFinalList;
}

合并时隙的最简单算法

easiest algorithm to merge time slots

algorithm

merge