Overlapping Ranges Check for Overlapping

Question

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

I have the following code. Which does not seem to be working. 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 generated list is 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 faced a challenge where I had to write a validating algorithm for ranges that are created by the user (integers or reals). I had to check 3 things:

1. Ranges are continuous
2. Ranges are not overlapping
3. LOW value must be always <= than HIGH

So I came up with the following PHP algorithm.

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

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

1. find overlapping ranges and raise an error
2. find start & end points in reverse and raise an error

If none of the above occurs, we count the difference of end - start points. This number must be equals to the number of ranges minus the step (1, 0.1, 0.01, etc). Otherwise we raise an error.

Hope this helps!

Answer 3

The solution to this problem can be as simple as writing your own RangeList : IList<Range> whose Add() method throws an exception when 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
}

Usage:

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

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

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