|
Максимально вложенный интервал | ☑ | ||
---|---|---|---|---|
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 Если эта таблица получилась пустая - это значит, что пересечения отсутствуют или интервалы повторяются. Если возможен такой вариант, значит просто добавляем объединение с основной таблицей. А потом просто ищем вхождения. |
Форум | Правила | Описание | Объявления | Секции | Поиск | Книга знаний | Вики-миста |