12

我有以下内容：

public class Interval
{
   DateTime Start;
   DateTime End; 
}

我有一个List<Interval>包含多个间隔的对象。我正在努力实现以下目标（我使用数字使其易于理解）：

[(1, 5), (2, 4), (3, 6)] --->  [(1,6)]
[(1, 3), (2, 4), (5, 8)] --->  [(1, 4), (5,8)]

我目前在 Python 中执行以下操作：

def merge(times):
    saved = list(times[0])
    for st, en in sorted([sorted(t) for t in times]):
        if st <= saved[1]:
            saved[1] = max(saved[1], en)
        else:
            yield tuple(saved)
            saved[0] = st
            saved[1] = en
    yield tuple(saved)

但我试图在 C# 中实现相同的效果（LINQ 是最好的但可选的）。关于如何有效地做到这一点的任何建议？

4

5 回答 5

14

这是一个使用的版本yield return- 我发现它比查询更容易阅读Aggregate，尽管它仍然是懒惰的评估。这假设您已经订购了列表，如果没有，只需添加该步骤。

IEnumerable<Interval> MergeOverlappingIntervals(IEnumerable<Interval> intervals)
{
  var accumulator = intervals.First();  
  intervals = intervals.Skip(1);

  foreach(var interval in intervals)
  {
    if ( interval.Start <= accumulator.End )
    {
        accumulator = Combine(accumulator, interval);
    }
    else
    {
        yield return accumulator;
        accumulator = interval;     
    }       
  }

  yield return accumulator;
}

Interval  Combine(Interval start, Interval end)
{
  return new Interval 
  {
    Start = start.Start,
    End = Max(start.End, end.End),
  };
}

private static DateTime Max(DateTime left, DateTime right) 
{
    return (left > right) ? left : right;
}
于 2012-07-14T02:03:23.010 回答
4

今晚我被“不是在这里创造”综合症所困扰，所以这是我的。使用枚举器直接为我节省了几行代码，使其更清晰（IMO），并处理了没有记录的案例。我想如果你关心它，它也可能会跑得更快......

public IEnumerable<Tuple<DateTime, DateTime>> Merge(IEnumerable<Tuple<DateTime, DateTime>> ranges)
{
    DateTime extentStart, extentEnd;
    using (var enumerator = ranges.OrderBy(r => r.Item1).GetEnumerator()) {
        bool recordsRemain = enumerator.MoveNext();
        while (recordsRemain)
        {
            extentStart = enumerator.Current.Item1;
            extentEnd = enumerator.Current.Item2;
            while ((recordsRemain = enumerator.MoveNext()) && enumerator.Current.Item1 < extentEnd)
            {
                if (enumerator.Current.Item2 > extentEnd)
                {
                    extentEnd = enumerator.Current.Item2;
                }
            }
            yield return Tuple.Create(extentStart, extentEnd);
        }
    }
}

在我自己的实现中，我使用一个TimeRange类型来存储 each Tuple<DateTime, DateTime>，就像这里的其他一样。我没有在这里包含它只是为了保持专注/关注主题。

于 2015-03-17T10:21:25.157 回答
3

这可能不是最漂亮的解决方案，但它也可以工作

public static List<Interval> Merge(List<Interval> intervals)
{
    var mergedIntervals = new List<Interval>();
    var orderedIntervals = intervals.OrderBy<Interval, DateTime>(x => x.Start).ToList<Interval>();

    DateTime start = orderedIntervals.First().Start;
    DateTime end = orderedIntervals.First().End;

    Interval currentInterval;
    for (int i = 1; i < orderedIntervals.Count; i++)
    {
        currentInterval = orderedIntervals[i];

        if (currentInterval.Start < end)
        {
            end = currentInterval.End;
        }
        else
        {
            mergedIntervals.Add(new Interval()
            {
                Start = start,
                End = end
            });

            start = currentInterval.Start;
            end = currentInterval.End;
        }
    }

    mergedIntervals.Add(new Interval()
                {
                    Start = start,
                    End = end
                });

    return mergedIntervals;
}

任何反馈将不胜感激。

问候

于 2012-07-14T01:24:45.823 回答
1

这种合并通常被视为函数式语言中的折叠。LINQ 等效项是Aggregate.

IEnumerable<Interval<T>> Merge<T>(IEnumerable<Interval<T>> intervals) 
  where T : IComparable<T>
{
    //error check parameters
    var ret = new List<Interval<T>>(intervals);
    int lastCount
    do
    {
        lastCount = ret.Count;
        ret = ret.Aggregate(new List<Interval<T>>(),
                    (agg, cur) =>
                    {
                        for (int i = 0; i < agg.Count; i++)
                        {
                            var a = agg[i];
                            if (a.Contains(cur.Start))
                            {
                                if (a.End.CompareTo(cur.End) <= 0)
                                {
                                    agg[i] = new Interval<T>(a.Start, cur.End);
                                }
                                return agg;
                            }
                            else if (a.Contains(cur.End))
                            {
                                if (a.Start.CompareTo(cur.Start) >= 0)
                                {
                                    agg[i] = new Interval<T>(cur.Start, a.End);
                                }
                                return agg;
                            }
                        }
                        agg.Add(cur);
                        return agg;
                    });
    } while (ret.Count != lastCount);
    return ret;
}

我创建了 Interval 类泛型 ( Interval<T> where T : IComparable<T>)，添加了一个bool Contains(T value)方法，并使其不可变，但如果您想像现在一样使用类定义，则不需要对其进行太多更改。

于 2012-07-14T01:53:43.617 回答
0

我使用 TimeRange 作为存储范围的容器：

public class TimeRange
{
    public TimeRange(DateTime s, DateTime e) { start = s;  end = e; }

    public DateTime start;
    public DateTime end;
}

它将问题划分为组合两个时间范围。因此，当前时间范围（工作）与之前合并的时间范围相匹配。如果先前添加的时间范围之一已过时，则将其删除并使用新的时间范围（结合工作和匹配的时间范围）。我想出的两个范围 () 和 [] 的情况如下：

  1. [] ()
  2. ([])
  3. [(])
  4. [()]
  5. ([)]

  6. ()[]

    public static IEnumerable<TimeRange> Merge(IEnumerable<TimeRange> timeRanges)
{
    List<TimeRange> mergedData = new List<TimeRange>();

    foreach (var work in timeRanges)
    {
        Debug.Assert(work.start <= work.end, "start date has to be smaller or equal to end date to be a valid TimeRange");
        var tr = new TimeRange(work.start, work.end);

        int idx = -1;
        for (int i = 0; i < mergedData.Count; i++)
        {
            if (tr.start < mergedData[i].start)
            {
                if (tr.end < mergedData[i].start)
                    continue;
                if (tr.end < mergedData[i].end)
                    tr.end = mergedData[i].end;
            }
            else if (tr.start < mergedData[i].end)
            {
                tr.start = mergedData[i].start;

                if (tr.end < mergedData[i].end)
                    tr.end = mergedData[i].end;
            }
            else
                continue;

            idx = i;
            mergedData.RemoveAt(i);
            i--;
        }

        if (idx < 0)
            idx = mergedData.Count;

        mergedData.Insert(idx, tr);
    }

    return mergedData;
}
于 2015-10-06T12:12:09.780 回答