Перекрывающиеся диапазоны Проверка на перекрытие

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

В прошлом я столкнулся с проблемой, где я должен был написать проверяющий алгоритм для диапазонов, которые создаются пользователем (целые или вещественные числа). Я должен был проверить 3 вещи:

1. Изменяется непрерывные
2. Изменяется не перекрывается
3. низкого значения должно быть всегда < = чем ВЫСОКИЙ

Так что я придумал следующий алгоритм 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 и т. Д.). В противном случае мы вызываем ошибку.

Надеюсь, это поможет!