C# 及时查找所有缺失的段

Question

我需要在 10 分钟内找到丢失的路段，我想知道最佳路线。

假设我有三个时间段。

1. 2:30 - 3:43 分钟部分。
2. 4:25 - 4:59 分钟片段。
3. 7:21 - 9:55 分钟片段。

使用 C#，我有一个完整的 10:20 分钟的时间段。当我已经从上面得到 3 个片段时，我需要找到缺失的片段。

所以我需要用C#计算的段如下

1. 0:00 - 2:29 分钟片段。
2. 3:44 - 4:24 分钟片段。
3. 5:00 - 7:20 分钟部分。
4. 9:56 - 10:20 分钟部分。

那么我是从上面已知的 3 个分割中计算出这 4 个分割吗？

我认为我最好的方法是只做一个 for 循环并一直计算到 10:20 秒，然后检查当前秒数是否存在于 3 个分段中。如果不是，请将那一秒添加到缺失的部分。

Answer 1

我不认为检查每一秒是否属于一个间隔是个好主意。我认为这个问题可以通过 O(n) complexity 来解决，当然使用一些 .NET 类来构造输入，这将使一切变得更容易。全提琴here .

private static List<Tuple<TimeSpan,TimeSpan>> ComputeMissingTimeSpans(List<Tuple<TimeSpan,TimeSpan>> availableIntervals, TimeSpan minSpan, TimeSpan maxSpan)
    {
        List<Tuple<TimeSpan,TimeSpan>> missingTime = new List<Tuple<TimeSpan,TimeSpan>>();
        if(availableIntervals.Count == 0)
        {
            missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, maxSpan));
            return missingTime;
        }

        foreach(var interval in availableIntervals){
            if((interval.Item1 - minSpan).TotalSeconds > 1 ) 
            {
                missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, interval.Item1.Add(TimeSpan.FromSeconds(-1))));
            }

            minSpan = interval.Item2.Add(TimeSpan.FromSeconds(1));
        }

        if((maxSpan - minSpan).TotalSeconds > 1)
            missingTime.Add(new Tuple<TimeSpan, TimeSpan>(minSpan, maxSpan));

        return missingTime;
    }

您可以根据自己的需要轻松调整此功能。