Имя: Пароль:
IT
 
Максимально вложенный интервал
,
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

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