重叠范围检查：检查是否存在重叠

Question

我有一组范围列表，希望找出它们是否重叠。

我有以下代码，但好像并不起作用。有没有更简单或有效的方法呢 :)

感谢您提前给予的任何建议。

   public partial class Form1 : Form
{
    public Form1()
    {
        InitializeComponent();
    }

    private IList<Range> rangeList;

    private void Form1_Load(object sender, EventArgs e)
    {
        rangeList.Add(new Range{FromNumber = 0, ToNumber = 100});
        rangeList.Add(new Range { FromNumber = 101, ToNumber = 200 });

        // this range should over lap and throw an exception 
        rangeList.Add(new Range { FromNumber = 199, ToNumber = 300 });

    }

    private bool RangesOverlap()
    {
        var bigList = new List<List<int>>();

        foreach (var range in this.rangeList)
        {
            bigList.Add(new List<int> { range.FromNumber , range.ToNumber });
        }

        IEnumerable<IEnumerable<int>> lists = bigList;

        return lists
         .Where(c => c != null && c.Any())
         .Aggregate(Enumerable.Intersect)
         .ToList().Count > 0;
    }
}


public class Range
{
    public int FromNumber { get; set; }
    public int ToNumber { get; set; }
}

- MicroMan

---

这似乎应该是一个新问题，而不是对现有问题的悬赏。Stack Overflow并不适合随着时间推移而发展的问题——这对那些回答了最初问题的人来说是不公平的，因为后来的任何人都会认为他们错过了重点。(另外，我不知道其他人怎么想，但我不理解悬赏中指定的要求...) - Jon Skeet

除了提交的答案外，我认为您可能会对以下事实感兴趣：您描述的问题基本上是“线段相交”问题的一个实例，最常用的解决方法是使用“扫描线算法”。也许深入研究一下可以回答您进一步的问题。 - Grx70

Answer 1

先合并数字，然后检查生成的列表是否按顺序排序：

rangeList
.OrderBy(p => p.FromNumber)
.Select(p => new[] { p.FromNumber, p.ToNumber })
.SelectMany(p => p)
.Aggregate((p, q) => q >= p ? q : int.MaxValue) == int.MaxValue

- Reza ArabQaeni

---

如果来自同一范围的起始值和结束值相等但在多个范围中没有重叠，我们需要如何修改呢？ rangeList.Add(new Range{FromNumber = 12, ToNumber = 12});rangeList.Add(new Range { FromNumber = 13, ToNumber = 20 }); - MicroMan

@Jeepers：我认为这对RezaArab有点不公平，因为他给了你一个很好的答案。现在你又添加了一个额外的问题，这可能意味着RezaArab失去了他的被接受的答案。 - Patrick Hofman

这里需要注意的是：此解决方案的前提是 rangeList 按 range.FromNumber 成员以升序排序。如果不是这样，请使用 rangeList.OrderBy(p => p.FromNumber).Select(...。 - Grx70

Answer 2

过去，我面临一个挑战，需要为用户创建的范围（整数或实数）编写验证算法。我需要检查以下三个方面：

1. 范围是连续的
2. 范围没有重叠
3. LOW值必须始终小于等于HIGH值

因此，我想出了以下PHP算法。

 //Let's hardcode an array of integers (it can be of reals as well):
 $range = array
 (
     array(1, 13),
     array(14, 20),
     array(21, 45),
     array(46, 50),
     array(51, 60)
 );

 //And the validation algorithm:
 $j = 0;
 $rows = sizeof($range);
 $step = 1;   // This indicates the step of the values.
              // 1 for integers, 0.1 or 0.01 for reals

 for ($x=0; $x<$rows; $x++)
     for ($y=0; $y<$rows; $y++) {
         if ( ($range[$x][0] <= $range[$y][0]) AND ($range[$y][0] <= $range[$x][1]) AND ($x != $y) ) {
             echo "Ranges intercepting";   // replace with error handling code
             break 3;
         }
         if ( $range[$x][0] > $range[$x][1] ) {
             echo "Not valid high & low";  // replace with error handling code
             break 3;
         }
         if ( $range[$x][0] - $range[$y][1] == $step ) {
             $j++;
         }
     }
 if ( $j != $rows - $step )
     echo "Not continuous";    // replace with error handling code

我们通过范围进行迭代，并将它们成对比较。针对每一对，我们会执行以下操作：

1. 找到重叠的范围并报错
2. 以相反的方式查找起始点和结束点并报错

如果以上情况均未发生，则计算结束点-起始点的差异。这个数字必须等于范围数量减去步长（1、0.1、0.01等）。否则就会报错。

希望这能帮到您！

- axs203dd

Answer 3

您可以通过稍微修改RezaArab的答案来满足您的新需求：

rangeList
.Select(p => new[] { p.FromNumber, p.ToNumber })
.SelectMany(p => p.Distinct())
.Aggregate((p, q) => q >= p ? q : int.MaxValue) == int.MaxValue

- Georg

Answer 4

解决这个问题的方法可能就是编写自己的RangeList：IList<Range>，其中Add()方法在指定的范围与已经存在于集合中的一个或多个范围重叠时抛出异常。

工作示例：

class Range
{
    public int FromNumber { get; set; }
    public int ToNumber { get; set; }

    public bool Intersects(Range range)
    {
        if ( this.FromNumber <= range.ToNumber )
        {
            return (this.ToNumber >= range.FromNumber);
        }
        else if ( this.ToNumber >= range.FromNumber )
        {
            return (this.FromNumber <= range.ToNumber);
        }

        return false;
    }
}

class RangeList : IList<Range>
{
    private readonly IList<Range> innerList;

    #region Constructors

    public RangeList()
    {
        this.innerList = new List<Range>();
    }

    public RangeList(int capacity)
    {
        this.innerList = new List<Range>(capacity);
    }

    public RangeList(IEnumerable<Range> collection)
    {
        if ( collection == null )
            throw new ArgumentNullException("collection");

        var overlap = from left in collection
                      from right in collection.SkipWhile(right => left != right)
                      where left != right
                      select left.Intersects(right);

        if ( overlap.SkipWhile(value => value == false).Any() )
            throw new ArgumentOutOfRangeException("collection", "The specified collection contains overlapping ranges.");

        this.innerList = new List<Range>(collection);
    }

    #endregion

    private bool IsUniqueRange(Range range)
    {
        if ( range == null )
            throw new ArgumentNullException("range");

        return !(this.innerList.Any(range.Intersects));
    }

    private Range EnsureUniqueRange(Range range)
    {
        if ( !IsUniqueRange(range) )
        {
            throw new ArgumentOutOfRangeException("range", "The specified range overlaps with one or more other ranges in this collection.");
        }

        return range;
    }

    public Range this[int index]
    {
        get
        {
            return this.innerList[index];
        }
        set
        {
            this.innerList[index] = EnsureUniqueRange(value);
        }
    }

    public void Insert(int index, Range item)
    {
        this.innerList.Insert(index, EnsureUniqueRange(item));
    }

    public void Add(Range item)
    {
        this.innerList.Add(EnsureUniqueRange(item));
    }

    #region Remaining implementation details

    public int IndexOf(Range item)
    {
        return this.innerList.IndexOf(item);
    }

    public void RemoveAt(int index)
    {
        this.innerList.RemoveAt(index);
    }

    public void Clear()
    {
        this.innerList.Clear();
    }

    public bool Contains(Range item)
    {
        return this.innerList.Contains(item);
    }

    public void CopyTo(Range[] array, int arrayIndex)
    {
        this.innerList.CopyTo(array, arrayIndex);
    }

    public int Count
    {
        get { return this.innerList.Count; }
    }

    public bool IsReadOnly
    {
        get { return this.innerList.IsReadOnly; }
    }

    public bool Remove(Range item)
    {
        return this.innerList.Remove(item);
    }

    public IEnumerator<Range> GetEnumerator()
    {
        return this.innerList.GetEnumerator();
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
    {
        return this.innerList.GetEnumerator();
    }

    #endregion
}

使用方法：

IList<Range> rangeList = new RangeList();

try
{
    rangeList.Add(new Range { FromNumber = 12, ToNumber = 12 });
    rangeList.Add(new Range { FromNumber = 13, ToNumber = 20 }); // should NOT overlap
    rangeList.Add(new Range { FromNumber = 12, ToNumber = 20 }); // should overlap
}
catch ( ArgumentOutOfRangeException exception )
{
    Console.WriteLine(exception.Message);
}

- Steven Liekens