sql программирование

Нахождение "дырок" в диапазонах с помощью SQL

Dmitry Vasiliev 18:40, 2008 8 4

Какое-то время назад мне подкинули следующую задачу:

В SQL базе есть таблица Ranges с двумя колонками start и end типа INT. В базе находятся диапазоны номеров и нужно найти "дырки" в диапазонах.

Например, для следующих диапазонов:

start end
10 10
10 20
20 30
25 40
50 60
55 57
65 100
70 80
77 90
101 200

Должны остаться вот такие "дырки":

start end
40 50
60 65

В первый момент мне показалось, что задача такого типа не совсем подходит для SQL базы, но в тоже время она похожа на классические задачи. Первым моим шагом было определение всех потенциальных "дырок":

SELECT r2.end, r1.start
    FROM Ranges r1, Ranges r2
    WHERE r1.start - r2.end > 1;

Это достаточно простой, практически, интуитивный шаг, но в результатах этого запроса слишком много лишнего. Следующий шаг оказался немного сложнее. Было понятно, что надо как-то "фильтровать" результаты предыдущего запроса, но пока не было точного алгоритма. Но в итоге я понял, что "дырками" могут быть только те найденные диапазоны которые никак не пересекаются с исходными диапазонами. Звучит достаточно просто и логично, но в практических задачах осознание простых фактов может занять достаточно много времени. :-) И я пришел к такому коду:

SELECT r2.end, r1.start
  FROM Ranges r1, Ranges r2
  WHERE r1.start - r2.end > 1
    AND NOT EXISTS (
      SELECT * FROM Ranges
      WHERE start < r1.start AND end > r2.end
      );

Думаю подход выше, который можно назвать как "найти потенциальные варианты и затем отфильтровать" может быть применим к большому классу задач с реляционными базами данных.

Comments All comments

Comment by goodguy on 21:12, 2008 8 4

goodguy's Gravatar

Слушай, а с учётом того, что в исходной таблице есть диапазон 10-10 и 10-20 не надо ли в результате фильтровать не просто по "меньше-больше" но и на равенство? (это так в порядке мелкой придирки, решение-то хорошее :))

Comment by Dmitry Vasiliev on 22:44, 2008 8 4

Dmitry Vasiliev's Gravatar

А они пропадают уже на первом этапе где r1.start - r2.end > 1. Собственно это условие определяет минимальный размер дырки и является "черновой" фильтрацией.

Теоретически можно условия "двигать" из первого запроса во второй и обратно, но мне кажется, что в данном случае получился баланс. :-)

Comment by Vasich on 10:12, 2008 8 6

Vasich's Gravatar

А почему во втором запросе в части NOT EXISTS буковки R1 и R2 большие?

Comment by Dmitry Vasiliev on 10:51, 2008 8 6

Dmitry Vasiliev's Gravatar

Потому что опечатка. :-)

Comment by SW on 22:40, 2008 9 6

SW's Gravatar

У меня на собеседовании пару раз такой вопрос задавли. В первый раз придумал сам за минут 10 ответ, который оказался правильным. Во второй раз пришлось придумывать заново, т.к. забыл :). Но во второй раз придумал оптимальнее.
Оба собеседования прошел успешно, кстати, но работать пошел совсем в другую компанию :).

Comment by Dmitry Vasiliev on 23:08, 2008 9 6

Dmitry Vasiliev's Gravatar

Как я понимаю этот вопрос косвенно от тебя и пришел. :-) А собеседования - это больше лотерея и поэтому есть много методов не проиграть для обоих сторон, но они не всегда помогают. ;-)

Add comment

Name:
Email: (Never will be published.)
Web site:
Comment: (Paragraphs divided by empty lines, line breaks and links will be automatically formatted.)