无限迭代器相交集的算法

Question

我必须实施类似于 Outlook Meeting Organizer 的调度算法，其中我有几个人参加会议，组织者找到邀请名单中的所有人都可用的时间段。假设我有一个实现以下接口的第三方服务：

interface IAvailabilityProvider
{
     IEnumerable<DateTimeInterval> GetPersonAvailableTimeSlots(
              string personName, DateTime startFrom);
}

其中 DateTimeInterval 是：

class DateTimeInterval{
   public DateTime Start {get;set;}
   public TimeSpan Length {get;set;}
}

GetPersonAvailableTimeSlots returns 无限迭代器，它会枚举一个人工作时间的所有时间段，不包括周末和假期之类的，无限到未来。

我的任务是实现一个函数，该函数采用一组这些迭代器和 returns 另一个交集迭代器：

IEnumerable<DateTimeInterval> GetIntersections(
    string[] persons, DateTime startFrom);

它获取所有人可用时隙的迭代器和 returns 相交时隙，当所有这些人都可用时。在内部我必须实现以下功能：

IEnumerable<DateTimeInterval> GetIntersections(
    IEnumerable<DateTimeInterval>[] personsAvailableSlots);

Answer 1

这个解决方案对我来说似乎很简单。

    static IEnumerable<DateTimeInterval> GetIntersections(IEnumerable<DateTimeInterval>[] personsAvailableSlots)
    {
        var enumerators = personsAvailableSlots.Select(timeline => timeline.GetEnumerator()).ToArray();

        // Intersection is empty when at least one of iterators is empty.
        for (int i = 0; i < personsAvailableSlots.Length; i++) if (!enumerators[i].MoveNext()) yield break;

        while (true)
        {
            // first we ensure that intersection exists at the current state
            // if not so, we have to move some iterators forward
            var start = enumerators.Select(tl => tl.Current).Max(interval => interval.Start);

            foreach (var iter in enumerators)
                while (iter.Current.Start + iter.Current.Length <= start)
                    if (!iter.MoveNext()) yield break;

            // now we check if the interval exists
            var int_start = enumerators.Select(tl => tl.Current).Max(interval => interval.Start);
            var int_end = enumerators.Select(tl => tl.Current).Min(interval => interval.Start + interval.Length);

            if (int_end > int_start)
            {
                //if so, we return it
                yield return new DateTimeInterval()
                {
                    Start = int_start,
                    Length = int_end - int_start
                };

                // and, finally, we ensure next interval to start after the current one ends
                //
                // CAUTION: We are able to move iterators whose current interval have passed only. 
                // We will miss huge spans which cover several intervals in other iterators otherwise.
                //
                // In fact we should move the only inerator - that one wich currently limits the last result
                foreach (var iter in enumerators)
                    while (iter.Current.Start + iter.Current.Length == int_end)
                        if (!iter.MoveNext()) yield break;
            } 
        }
    }

我已经针对几个简单的场景对此进行了测试，希望我没有遗漏一些重要的东西。

无限迭代器相交集的算法

Algorithm of intersecting set of infinite Iterators

c#

algorithm

iterator

infinite-loop