重叠范围检查重叠

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

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 

Answer 2

您可以RezaArabs稍加改进满足新的要求回答：

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

Answer 3

解决方案对于这个问题，可以像编写自己的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); 
} 

Answer 4

在我遇到，我只好写了由用户创建的范围进行验证的算法是一个挑战过去（整数或实数）。我不得不检查三件事情：

1. 范围是连续
2. 范围不会重叠
3. LOW值必须始终< =比高

于是我想出了下面的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等）。否则，我们提出一个错误。

希望这会有所帮助！