重疊範圍檢查重疊

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等）。否則，我們提出一個錯誤。

希望這會有所幫助！