什么是良好的，通用的算法倒塌了一套潜在的重叠范围？ [英] What's a good, generic algorithm for collapsing a set of potentially-overlapping ranges?

问题描述

我有一个得到了一些此类的对象的方法

I have a method that gets a number of objects of this class

class Range<T>
{
    public T Start;
    public T End;
}

在我的情况下 T 是的DateTime ，但让使用 INT 的简单性。我想坍塌的范围为那些覆盖相同的区域，但不重叠的方法。

In my case T is DateTime, but lets use int for simplicity. I would like a method that collapses those ranges into ones that cover the same "area" but that do not overlap.

所以，如果我有以下范围

So if I had the following ranges

• 在1到5
• 3〜9
• 11〜15
• 在12至14
• 在13至20

该方法应该给我

• 1〜9
• 在11至20

想它会被称为工会？我想象中的方法签名可能看起来是这样的：

Guess it would be called a union? I imagine the method signature could look something like this:

public static IEnumerable<Range<T>> Collapse<T>(
    this IEnumerable<Range<T>>, 
    IComparable<T> comparer)
{
    ...
}

我已经在这里看到一些其他的问题，这是一种类似，但我还没有找到一个这样的实现呢。 <一href="http://stackoverflow.com/questions/149577/need-an-algorithm-for-collapsing-netblock-ranges-into-lists-of-superset-ranges/149829#149829">This回答以及一些其他的答案对同一问题描述算法，但我不能肯定，如果我理解的算法。不特别是在执行算法是好，所以我希望这里有人可以帮助我。

I have looked at some other questions here that are kind of similar, but I haven't found an implementation of this yet. This answer and some other answers to the same question describes algorithms, but I am not quite sure if I understand the algorithms. Not especially good at implementing algorithms either, so I was hoping someone here could help me out.

推荐答案

这似乎工作，很容易理解。

This seems to works and is easy to understand.

    public static IEnumerable<Range<T>> Collapse<T>(this IEnumerable<Range<T>> me, IComparer<T> comparer)
    {
        List<Range<T>> orderdList = me.OrderBy(r => r.Start).ToList();
        List<Range<T>> newList = new List<Range<T>>();

        T max = orderdList[0].End;
        T min = orderdList[0].Start;

        foreach (var item in orderdList.Skip(1))
        {
            if (comparer.Compare(item.End, max) > 0 && comparer.Compare(item.Start, max) > 0)
            {
                newList.Add(new Range<T> { Start = min, End = max });
                min = item.Start;
            }
            max = comparer.Compare(max, item.End) > 0 ? max : item.End;
        }
        newList.Add(new Range<T>{Start=min,End=max});

        return newList;
    }

---

---

下面是我在评论中提到的变化。它基本上是同样的事情，但也有一些检查和产生的结果，而不是收集在一个列表中返回。

Here is the variation which I mentioned in the comments. It's basically the same thing, but with some checking and yielding of the results instead of collecting in a list before returning.

    public static IEnumerable<Range<T>> Collapse<T>(this IEnumerable<Range<T>> ranges, IComparer<T> comparer)
    {
        if(ranges == null || !ranges.Any())
            yield break;

        if (comparer == null)
            comparer = Comparer<T>.Default;

        var orderdList = ranges.OrderBy(r => r.Start);
        var firstRange = orderdList.First();

        T min = firstRange.Start;
        T max = firstRange.End;

        foreach (var current in orderdList.Skip(1))
        {
            if (comparer.Compare(current.End, max) > 0 && comparer.Compare(current.Start, max) > 0)
            {
                yield return Create(min, max);
                min = current.Start;
            }
            max = comparer.Compare(max, current.End) > 0 ? max : current.End;
        }
        yield return Create(min, max);
    }

这篇关于什么是良好的，通用的算法倒塌了一套潜在的重叠范围？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！