折叠一组可能重叠的范围有什么好的通用算法？

Question

我有一个方法可以获得这个类的许多对象

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

在我的情况T是DateTime,但让我们使用int的简便性.我想要一种方法,将这些范围折叠成覆盖相同"区域"但不重叠的区域.

所以,如果我有以下范围

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

该方法应该给我

• 1至9
• 11至20

猜猜它会被称为联盟？我想方法签名看起来像这样:

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

我在这里看了一些类似的其他问题,但我还没有找到它的实现.这个答案和同一问题的其他一些答案描述了算法,但我不太清楚我是否理解算法.也不是特别擅长实现算法,所以我希望有人可以帮助我.

Answer 1

这似乎有效并且易于理解.

    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;
    }

这是我在评论中提到的变体.它基本上是相同的,但有一些检查和结果,而不是在返回之前收集列表.

    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);
    }

Answer 2

非verbosephile的Python解决方案:

ranges = [
  (11, 15),
  (3, 9),
  (12, 14),
  (13, 20),
  (1, 5)]

result = []
cur = None
for start, stop in sorted(ranges): # sorts by start
  if cur is None:
    cur = (start, stop)
    continue
  cStart, cStop = cur
  if start <= cStop:
    cur = (cStart, max(stop, cStop))
  else:
    result.append(cur)
    cur = (start, stop)
result.append(cur)

print result