我有一个方法可以获取这个类的一些对象
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)
{
...
}
我在这里查看了其他一些类似的问题,但我还没有找到它的实现。 This answer和同一个问题的其他一些答案描述了算法,但我不太确定我是否理解这些算法。也不是特别擅长实现算法,所以我希望这里有人能帮助我。
最佳答案
这似乎有效并且很容易理解。
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);
}
关于c# - 什么是折叠一组潜在重叠范围的通用算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1233292/