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

Soulful

It feels like this should be a new question rather than bounty on an existing one. Stack Overflow doesn't really work well with questions that evolve over time - it's not fair on people who answered the initial question, as anyone coming later on will think they missed the point. (Also, I don't know about anyone else, but I don't understand the requirements specified in the bounty...) – Buroker

Apart from submitted answers I think you may be interested in the fact that the problem you described is basically an instance of the 'line segment intersection' problem, most commonly solved using 'sweep line algorithm'. Perhaps reading more into it could provide answers to your further questions. – Appointive

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

Pasto

If the To and the From from a single range can be equal but not overlap on multiple ranges. How would we need to alter this? rangeList.Add(new Range{FromNumber = 12, ToNumber = 12}); rangeList.Add(new Range { FromNumber = 13, ToNumber = 20 }); – Soulful

@Jeepers: I think this is a little unfair to RezaArab, since he gave you an excellent answer. Now you are adding an additional question, which could mean that RezaArab looses his accepted answer. – Anglophobe

Just a note here: this solution works under the assumption that the rangeList is sorted in ascending order by the range.FromNumber member. If it may not be true, just use rangeList.OrderBy(p => p.FromNumber).Select(... – Appointive

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!

Alkali

Answer 3

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

Lurlenelurline

Answer 4

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

Molest