最佳的方式根据预测点组的时间间隔 [英] Optimal way to group time intervals based on projected points

问题描述

假设我们已经整理的时间间隔列表（排序开始的时间）。 我正在寻找最佳的解决方案，以项目这些间隔为轴线，其结果对象的数组，描述：预计发车间隔和放大器;结束时间和来源间隔阵列陷入预计intevals

Imagine we have sorted list of time intervals (sorted by time of beginning). I'm looking for optimal solution to 'project' these intervals to axis, having as a result an array of objects, describing: projected interval start&end time and arrays of source intervals that fall into projected intevals.

让我的例子来说明：假设我们有4个间隔为输入（按开始时间排序，然后按结束时间）：

Let me explain on example: imagine we have 4 intervals as input (sorted by start time, then by end time):

   [---R1---)    
         [-----R2-----)
         [---------R3-------)
                 [----R4----)

 --|-----|--|----|----|-----|---> t (time axis)
      1    3   2    3    2 

在这种情况下，我期待得到的5个元素的数组，每个元素是描述区间的开始/结束和源区间的列表的对象。在图表上的轴号显示在列表中的项目数量。

In that case I'm expecting to get array of 5 elements, each element is an object describing interval start/end and a list of source intervals. Numbers under axis on chart shows number of items in that list.

请帮我找到最快的解决这一任务的方式

Please, help me to find fastest way to solve this task

推荐答案

最后，我已经找到了最有效的方式。它使用一个排序操作和O（N * 2）重复建设造成的。

Finally I've found the most effective way. It uses one sorting operation and O(N*2) iterations to build result.

public IEnumerable<DateProjectedItems<T>> Project(IList<T> items)
{
    if (items.Count <= 1)
    {
        if (items.Count == 0)
        {
            yield break;
        }
        yield return new DateProjectedItems<T>
        {
            DateRange = items[0].DateRange,
            Items = items
        };
    }
    else
    {
        var endOrdered = items.OrderBy(i => i.DateRange.DateTimeTo).ToList();
        var active = new List<T>();
        DateTime? last = null;                
        foreach (var pair in TwoArrayIterator(items, endOrdered))
        {
            DateTime current = pair.Key == 1 ? pair.Value.DateRange.DateTimeFrom : pair.Value.DateRange.DateTimeTo;
            if (last != null && current != last)
            {
                yield return new DateProjectedItems<T>
                {
                    DateRange = new DateRange(last.Value, current),
                    Items = active.ToList()
                };
            }
            if (pair.Key == 1)
            {
                active.Add(pair.Value);
            }
            else
            {
                active.Remove(pair.Value);
            }
            last = current;
        }             
    }
}

public IEnumerable<KeyValuePair<int, T>> TwoArrayIterator(IList<T> arr1, IList<T> arr2)
{
    var index1 = 0;
    var index2 = 0;
    while (index1 < arr1.Count || index2 < arr2.Count)
    {
        if (index1 >= arr1.Count)
            yield return new KeyValuePair<int, T>(2, arr2[index2++]);
        else if (index2 >= arr2.Count)
            yield return new KeyValuePair<int, T>(1, arr1[index1++]);
        else
        {
            var elt1 = arr1[index1];
            var elt2 = arr2[index2];
            if (elt1.DateRange.DateTimeFrom < elt2.DateRange.DateTimeTo)
            {
                index1++;
                yield return new KeyValuePair<int, T>(1, elt1);
            }
            else
            {
                index2++;
                yield return new KeyValuePair<int, T>(2, elt2);
            }
        }
    }
} 

这篇关于最佳的方式根据预测点组的时间间隔的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！