Overlapping ranges Overlap check

Question

I have a list of ranges and I would like to know if they overlap.

I have the following code. This does not seem to work. Is there an easier way to do this or a way that works :)

Thanks in advance for any advice.

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

First merge numbers, and then check the generated list in sorted order:

 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

In the past, I ran into a problem when I had to write a verification algorithm for ranges created by the user (integers or numbers). I had to check 3 things:

• Ranges continuous
• Ranges do not overlap
• LOW must always be <= than HIGH

So, I came up with the following PHP algorithm.

  //Let 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 

We iterate over the ranges and compare them in pairs. For each pair we have:

• find overlapping ranges and raise the error.
• find the start and end points in reverse order and raise the error.

If none of the above happens, we take into account the difference in the start points. This number should be equal to the number of ranges minus the step (1, 0.1, 0.01, etc.). Otherwise, we cause an error.

Hope this helps!

Answer 3

You can fulfill your new requirement with a slight modification of the RezaArabs answer:

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

Answer 4

The solution to this problem can be as simple as writing your own RangeList : IList<Range> , whose Add() method throws an exception if the specified range overlaps with one or more ranges that are already in the collection.

Working example:

 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 } 

Using:

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