Например, для следующих диапазонов:
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
Слушай, а с учётом того, что в исходной таблице есть диапазон 10-10 и 10-20 не надо ли в результате фильтровать не просто по "меньше-больше" но и на равенство? (это так в порядке мелкой придирки, решение-то хорошее :))
Comment by Dmitry Vasiliev on 22:44, 2008 8 4
А они пропадают уже на первом этапе где r1.start - r2.end > 1. Собственно это условие определяет минимальный размер дырки и является "черновой" фильтрацией.
Теоретически можно условия "двигать" из первого запроса во второй и обратно, но мне кажется, что в данном случае получился баланс. :-)
Comment by Vasich on 10:12, 2008 8 6
А почему во втором запросе в части NOT EXISTS буковки R1 и R2 большие?
Comment by Dmitry Vasiliev on 10:51, 2008 8 6
Потому что опечатка. :-)
Comment by SW on 22:40, 2008 9 6
У меня на собеседовании пару раз такой вопрос задавли. В первый раз придумал сам за минут 10 ответ, который оказался правильным. Во второй раз пришлось придумывать заново, т.к. забыл :). Но во второй раз придумал оптимальнее.
Оба собеседования прошел успешно, кстати, но работать пошел совсем в другую компанию :).
Comment by Dmitry Vasiliev on 23:08, 2008 9 6
Как я понимаю этот вопрос косвенно от тебя и пришел. :-) А собеседования - это больше лотерея и поэтому есть много методов не проиграть для обоих сторон, но они не всегда помогают. ;-)
Add comment