я хочу добавить скоростные диапазоны с небольшими суммами и сохранить их в базе данных

Question

.. здесь моя проблема в том, что я должен проверить, перекрываются или нет диапазоны скоростей, и если они перекрываются, я должен отобразить сообщение о том, что диапазоны скоростей не могут перекрываться.

Minimum  Maximum     Rate
1           15        10

16          25        15 

Answer 1

Думайте о каждом диапазоне скоростей как о отрезке на непрерывной числовой линии.Чтобы найти все перекрытия, разделите числовую линию на каждое перекрытие сегмента.

Сначала разделите каждый диапазон на начальную и конечную точки.Допустим, ваши диапазоны:

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

Я собираюсь назначить им буквы для ясности:

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

Хорошо, теперьДавайте разделим эти диапазоны на отдельные начальные и конечные точки:

A[start]=5, A[end]=8, B[start]=1, B[end]=5, C[start]=14, C[end]=... и т. д.

Сортируем эти точки по значению, где, если значения равны, начальная точка предшествуетконечная точка, так что вы получите список, подобный следующему:

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

Легко, верно?

Теперь просто переберите отсортированный список, сохраняясписок текущих диапазонов.Каждый раз, когда вы приходите к точке [start], добавляйте этот диапазон в список.Каждый раз, когда вы приходите к точке [end], вынимайте диапазон из списка.

Так что для списка выше вы должны идти:

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

Каждый раз, когда ваш список содержит большечем один элемент, это совпадение.Таким образом, для любого диапазона вы можете точно определить, какие диапазоны перекрываются в любой конкретной точке.

Предполагается, что вы используете алгоритм, такой как быстрая сортировка, для сортировки текущих / конечных точек, это будет O(n log n) времени выполнения, и обнаружениефактические перекрытия линейны по времени, поэтому весь алгоритм будет работать в O(n log n).

Answer 2

Вы могли бы легко реализовать эту бизнес-логику в своей базе данных, чтобы требовать от любых будущих приложений соблюдения этого ограничения.

Я бы реализовал логику как хранимую процедуру (или триггер) с чем-то вроде этого:

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

Тогда в вашем приложении, если возвращается -1, покажите сообщение об ошибке по вашему выбору.

Answer 3

Если вы сортируете значения:

• Сначала на нижней границе
• Тогда на верхней границе

Затем вы можете выполнять их последовательную итерацию и сравнивать один диапазон со следующим. Перекрывающиеся диапазоны будут рядом друг с другом в последовательности.

В вашем примере:

• Сравните 1-16 с 10-15 (перекрытие)
• Сравните 10-15 с 15-25 (возможное перекрытие зависит от того, как вы определяете перекрытие)

Обратите внимание, однако, что этот алгоритм отвечает только на вопрос «перекрывает ли любой диапазон», он не дает вам все перекрывающиеся комбинации. Например, в приведенном выше коде 1-16 и 15-25 перекрываются, но вы не получите эту комбинацию с этой реализацией.

Если вам это требуется, вам нужен гораздо более умный алгоритм.

Я разместил здесь проект Visual Studio 2008: Хранилище Subversion для SO2696398 .

Основной код приложения выглядит следующим образом:

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

Вывод:

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]

Надеюсь, это поможет. Часть классов проекта - это небольшое подмножество классов, которые есть в моей библиотеке основных классов. Если вы предпочитаете ссылаться на полную библиотеку, вы можете скачать и скомпилировать исходный код из Subversion Repository for LVK для .NET . Используемые здесь классы взяты из проекта LVK.Core.