i want to add speed ranges with some fine amounts and save them into databse

Question

..here my problem is i should check whether the speed ranges overlap or not and if they overlap i should display a message saying the speed ranges cannot be overlapped.

Minimum  Maximum     Rate
1           15        10

16          25        15 

Answer 1

If you sort the values:

• First on the lower bound
• Then on the upper bound

Then you can iterate through them in sequence, and check one range against the next. Overlapping ranges will be next to each other in the sequence.

In your example:

• Compare 1-16 with 10-15 (overlap)
• Compare 10-15 with 15-25 (possible overlap, depends on how you define overlap)

Note, however, that this algorithm only answers the question "does any ranges overlap", it does not give you all overlapping combinations. For instance, in the above code, 1-16 and 15-25 overlap, but you're not getting that combination with this implementation.

If you require that, you require a much smarter algorithm.

I've posted a Visual Studio 2008 project here: Subversion Repository for SO2696398.

The main application code looks like this:

using System;
using System.Linq;
using LVK.Collections;

namespace SO2696398
{
    public class Program
    {
        public static void Main(string[] args)
        {
            var ranges = new[]
            {
                new Range<int, double>(1, 15, 10),
                new Range<int, double>(16, 25, 15),
                new Range<int, double>(8, 22, 7),
            };
            var slices = ranges.Ordered<int, double>().Slice();

            foreach (var slice in slices)
            {
                if (slice.Data.Length == 1)
                    continue;

                Console.Out.WriteLine("overlap at " + slice.Start
                    + "-" + slice.End + ": "
                    + string.Join(" with ",
                    (from range in slice.Data
                     select range.ToString() 
                     + " [rate=" + range.Data + "]").ToArray()));
            }
        }
    }
}

The output is:

overlap at 8-15: 1..15 [rate=10] with 8..22 [rate=7]
overlap at 16-22: 8..22 [rate=7] with 16..25 [rate=15]

Hope this helps. The classes part of the project is a small subset of the classes I have in my main class library. If you'd rather link to the full library, you can download and compile the source code from Subversion Repository for LVK for .NET. The classes used here is from the LVK.Core project.

Answer 2

Think of each speed range as a line segment on a continuous number line. In order to find all the overlaps, partition the number line at every line segment overlap.

First, separate each range into a start and end point. Let's say your ranges are:

(5,8) (1,5) (14,17) (3,4) (5,10)

I'm going to assign them letters for clarity:

A=(5,8) B=(1,5) C=(14,17) D=(3,4) E=(5,10)

Okay, now, let's split these ranges into discrete start and end points:

A[start]=5, A[end]=8, B[start]=1, B[end]=5, C[start]=14, C[end]=... etc.

Sort these points by the value, where in case the values are equal, the start point comes before the end point, so that you get a list like this:

B[start]=1, D[start]=3, D[end]=4, A[start]=5, E[start]=5, B[end]=5, A[end]=8, ... etc.

Easy, right?

Now, just iterate over your sorted list, keeping a list of the current ranges. Every time you come to a [start] point, add that range to the list. Every time you come to an [end] point, take the range out of the list.

So for the list above, you'd go:

B[start]=1  add B =>    (B)
D[start]=3  add D =>    (B,D)
D[end]=3    remove D => (B)
A[start]=4  add A =>    (B,A)
E[start]=5  add E =>    (B,A,E)
B[end]=5    remove B => (A,E)
A[end]=8    remove A => (E)
  ... and so on

Anytime your list contains more than a single element, that's an overlap. So for any range, you can determine exactly which ranges overlap at any particular point.

Assuming you use an algorithm like quicksort to sort the being/end points, that will be O(n log n) running time, and detecting the actual overlaps is linear in time, so the whole algorithm will run in O(n log n).

Answer 3

You could easily implement this business logic in your database to require any future applications to follow this constraint.

I would implement the logic as a stored procedure (or trigger) with something like this:

CREATE PROCEDURE MyDatabase.spInsertSpeedRanges
    @Min int, 
    @Max int,
    @Rate int
AS

select top 1 * 
from tblSpeedRanges 
where (Minimum between @Min and @Max) or (Maximum between @Min and @Max)

if @@RowCount <> 0
  return -1
else
  insert into tblSpeedRanges (Minimum, Maximum, Rate) values (@Min, @Max, @Rate)

GO

Then in your application, if -1 is returned, show the error message of your choice.