|
Максимально вложенный интервал |
☑ |
0
Ненавижу 1С
гуру
27.10.11
✎
09:04
|
Есть таблица Т со столбцами Т1, Т2 - целые числа, для каждой строки верно Т1<Т2. Каждую строку интерпретируем как открытый интервал (Т1,Т2).
Требуется найти ЗАПРОСОМ 1С интервал (возможно их будет несколько), вложенный в максимальное число интервалов, указанных в строках таблицы.
Пример
1 5
2 7
4 6
7 10
Ответ: (4,5) - 3 вложения
|
|
1
Mielle
27.10.11
✎
09:14
|
А всякие временные таблицы можно юзать?
|
|
2
Ненавижу 1С
гуру
27.10.11
✎
09:15
|
(1) да
|
|
3
Ненавижу 1С
гуру
27.10.11
✎
09:16
|
+(2) один фиг они реализуются подзапросами (хотя неоптимально)
|
|
4
Evpatiy
27.10.11
✎
09:43
|
(0) "Требуется найти ЗАПРОСОМ 1С"
Какой изощренный способ переложить свою задачу на не знакомых людей :)
Либо секцию смените на 1С, либо давайте рассуждать в терминах реляционной алгебры и оставим в секции "математика и алгоритмы"
|
|
5
Ненавижу 1С
гуру
27.10.11
✎
09:44
|
(4) да ни разу не прав ты
просто навеяло темой Задача про временные интервалы
|
|
6
Evil-Wisp
27.10.11
✎
09:56
|
(0) Где у тебя в примере строка с интервалом (4,5)?
У 3-й строки 2 вложения, и она максимально вложена. (4,6)
|
|
7
Ненавижу 1С
гуру
27.10.11
✎
10:00
|
(6) а он и не обязан быть из этих строк, просто (4,5) входит сразу в 3 интервала, а (4,6) только в 2
|
|
8
1Сергей
27.10.11
✎
10:06
|
1. xxxxx-----
2. -xxxxxx---
3. ---xxx----
4. ------xxxx
|
|
9
Evpatiy
27.10.11
✎
10:19
|
Топорно можно набрать все возможные промежутки в таблицу. То есть все пары Т1,Т2 для которых Т2>=Т1. И посчитать для каждого количество вхождений в исходную таблицу.
|
|
10
ptiz
27.10.11
✎
10:49
|
Вроде просто всё, главное - получить список интервалов.
Например, соединяем ТЗ саму с собой:
ВЫБРАТЬ
ТЗ1.Т1,
ТЗ2.Т2
ПОМЕСТИТЬ ТЗВнутренниеИнтервалы
ИЗ
ТЗ КАК ТЗ1
ВНУТРЕННЕЕ СОЕДИНЕНИЕ ТЗ КАК ТЗ2
ПО ТЗ1.Т1 < ТЗ2.Т2
И ТЗ1.Т1 > ТЗ2.Т1
И ТЗ1.Т2 > ТЗ2.Т2
Если эта таблица получилась пустая - это значит, что пересечения отсутствуют или интервалы повторяются. Если возможен такой вариант, значит просто добавляем объединение с основной таблицей.
А потом просто ищем вхождения.
|
|