Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Oracle Новый топик    Ответить
 Задачка интересная  [new]
nagisa
Member

Откуда: Красноярск
Сообщений: 143
есть табличка с числовыми полями beg и end
в них хранятся диапазоны - с 10 по 20 с 12-15 итд
близкий физический смысл - отрезки
стоит задача подсчитать "покрытую" площать
те в если табличке:
beg end
10 20
12 15
35 40

то "площадь" будет считаться по максимальному перекрытию - те (20-10)+(40-35)=10+5 а строка с 12-15 не попадает так как есть больший отрезок 10-20
условия:
- вложенность не ограничена
- вложенность обязательна
те не может быть данных вида:
10-20
15-35
11 май 06, 09:12    [2650604]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
dmidek
Member

Откуда: Киев - Дортмунд
Сообщений: 116138
В лоб

select sum(end-beg) from square a
where not exists
(select null from square
 where beg < a.beg
 and end > a.end)
11 май 06, 09:18    [2650635]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Dimkas
Member

Откуда: Красноярск
Сообщений: 403
первая мысль (для разгона тсзть):
1. вычислить длину каждого отрезка и поместить в отдельное поле
2. выбрать отрезок с максимальной длиной
3. удалить из обработки все отрезки входящие в отрезок, выбранный в п.2
4. отрезок в максимальной длиной отметить как "посчитанный"
5. повторять для непосчитанных до упора
6. сложить сумму посчитанных...

с уважением,
Дмитрий Жучков
11 май 06, 09:19    [2650640]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Dimkas
Member

Откуда: Красноярск
Сообщений: 403
dmidek
select sum(end-beg) from square a
where not exists
(select null from square
 where beg < a.beg
 and end > a.end)

на минуту позже дословно повторил на русском :)
11 май 06, 09:23    [2650655]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Elic
Member

Откуда:
Сообщений: 29979
STFF работа с временными интервалами, Периоды, объединение
11 май 06, 09:25    [2650663]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
nagisa
Member

Откуда: Красноярск
Сообщений: 143
Dimkas
dmidek
select sum(end-beg) from square a
where not exists
(select null from square
 where beg < a.beg
 and end > a.end)

на минуту позже дословно повторил на русском :)


вот так правильно - тк начало или конец могут совпадать
select sum(end-beg) from square a
where not exists
(select null from square
where beg <= a.beg
and end >= a.end)
11 май 06, 09:33    [2650693]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
nagisa
Member

Откуда: Красноярск
Сообщений: 143
что-то ошибся я - не катит решение
не все пересечения находит
из ~700 ~60 остается

так что вопрос открытый
11 май 06, 09:40    [2650710]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Elic
Member

Откуда:
Сообщений: 29979
nagisa
вот так правильно - тк начало или конец могут совпадать
select sum(end-beg) from square a
where not exists
(select null from square
where beg <= a.beg
and end >= a.end
)
Исключает каждого как самоё себя :)
11 май 06, 09:53    [2650784]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Ewg_
Member

Откуда: Moskow Region
Сообщений: 365
а что собираешься делать если данные
10 20
15 25 ?
11 май 06, 10:48    [2651147]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
dmidek
Member

Откуда: Киев - Дортмунд
Сообщений: 116138
nagisa
- вложенность обязательна
те не может быть данных вида:
10-20
15-35


Ewg
а что собираешься делать если данные
10 20
15 25 ?
11 май 06, 10:50    [2651166]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Я
Guest
dmidek
В лоб

select sum(end-beg) from square a
where not exists
(select null from square
 where beg < a.beg
 and end > a.end)
Это работать не будет!!!
11 май 06, 10:52    [2651174]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
nagisa
Member

Откуда: Красноярск
Сообщений: 143
Elic
Исключает каждого как самоё себя :)

я уже написал что ошибся ;-)

а вот так работает:

select sum(end-beg) from square a
where not exists
(select null from square
where beg < a.beg
and end > a.end
and id<>a.id )

где id - уникальный идентификатор диапазона
11 май 06, 10:56    [2651217]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
nagisa
Member

Откуда: Красноярск
Сообщений: 143
в смысле
select sum(end-beg) from square a
where not exists
(select null from square
where beg <= a.beg
and end >= a.end
and id<>a.id )
11 май 06, 10:58    [2651229]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Ewg_
Member

Откуда: Moskow Region
Сообщений: 365
а почему не так?
select sum(end-beg) from square a
where not exists
(select null from square
 where beg <= a.beg
 and end >= a.end
 and ( beg <> a.beg or  end <> a.end )
)

заодно будем пропускать дублирующиеся данные
11 май 06, 11:00    [2651253]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
nagisa
в смысле
select sum(end-beg) from square a
where not exists
(select null from square
where beg <= a.beg
and end >= a.end
and id<>a.id )
А мне кажеться, что "Я" прав. Если я правильно понял задачу, то вот на таком наборе данных:
with t 
  as (
        select  1 as id,  1 as b,  5 as e from dual union all
        select  2 as id,  3 as b,  7 as e from dual union all
        select  3 as id,  3 as b,  4 as e from dual union all
        select  4 as id,  9 as b, 15 as e from dual union all
        select  5 as id, 10 as b, 20 as e from dual union all
        select  6 as id, 18 as b, 19 as e from dual union all
        select  7 as id, 18 as b, 25 as e from dual union all
        select  8 as id, 30 as b, 35 as e from dual union all
        select  9 as id, 40 as b, 45 as e from dual union all
        select 10 as id, 50 as b, 55 as e from dual
     ) 
select sum(e-b) 
  from t a
 where not exists (
                     select null 
                       from t
                      where b <= a.b
                        and e >= a.e
                        and id<>a.id
                  )
должен получиться результат 37, а получается 46...
11 май 06, 11:04    [2651288]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
nagisa
Member

Откуда: Красноярск
Сообщений: 143
да
тоже работает - по времени одинаково с первым
11 май 06, 11:04    [2651289]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
dmidek
Member

Откуда: Киев - Дортмунд
Сообщений: 116138
Владимор Конев
nagisa
в смысле
select sum(end-beg) from square a
where not exists
(select null from square
where beg <= a.beg
and end >= a.end
and id<>a.id )
А мне кажеться, что "Я" прав. Если я правильно понял задачу, то вот на таком наборе данных:
with t 
  as (
        select  1 as id,  1 as b,  5 as e from dual union all
        select  2 as id,  3 as b,  7 as e from dual union all
        select  3 as id,  3 as b,  4 as e from dual union all
        select  4 as id,  9 as b, 15 as e from dual union all
        select  5 as id, 10 as b, 20 as e from dual union all
        select  6 as id, 18 as b, 19 as e from dual union all
        select  7 as id, 18 as b, 25 as e from dual union all
        select  8 as id, 30 as b, 35 as e from dual union all
        select  9 as id, 40 as b, 45 as e from dual union all
        select 10 as id, 50 as b, 55 as e from dual
     ) 
select sum(e-b) 
  from t a
 where not exists (
                     select null 
                       from t
                      where b <= a.b
                        and e >= a.e
                        and id<>a.id
                  )
должен получиться результат 37, а получается 46...

Но ведь 10 - 20 и 18 - 25 - пересекающиеся интервалы, а таковых у нас на должно быть ....
11 май 06, 11:10    [2651335]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Ewg_
Member

Откуда: Moskow Region
Сообщений: 365
Владимор Конев

select 1 as id, 1 as b, 5 as e from dual union all
select 2 as id, 3 as b, 7 as e from dual union all

сказали интервалы не могут пересекаться... :)

2 nagisa: тема закрыта? задача решена?
11 май 06, 11:10    [2651336]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
dmidek
Но ведь 10 - 20 и 18 - 25 - пересекающиеся интервалы, а таковых у нас на должно быть ....
Это не следует из сообщения автора :)
11 май 06, 11:16    [2651368]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Владимор Конев
Member

Откуда:
Сообщений: 3451
Владимор Конев
dmidek
Но ведь 10 - 20 и 18 - 25 - пересекающиеся интервалы, а таковых у нас на должно быть ....
Это не следует из сообщения автора :)
Хотя пардон, не увидел последнего предложения в первом посте от автора :)
11 май 06, 11:17    [2651378]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Колобок
Member

Откуда:
Сообщений: 122
Вот ещё вариант без exists:

select sum(end-beg)
from (select beg, end,
             lag(end) over (order by beg) prev_end
        from square)
 where prev_end is null
    or prev_end <= beg;

<= на случай если такие данные правильные:
10 20
20 25
Если неправильные - можно "<", хотя и так будет работать.
11 май 06, 11:30    [2651451]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Elic
Member

Откуда:
Сообщений: 29979
Колобок
Вот ещё вариант без exists:
select sum(end-beg)
from (select beg, end,
             lag(end) over (order by beg) prev_end
        from square)
 where prev_end is null
    or prev_end <= beg;
И где наша фантазия: ((10,20),(12,14),(16,17)) ?
11 май 06, 11:46    [2651541]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
Колобок
Member

Откуда:
Сообщений: 122
Elic
И где наша фантазия: ((10,20),(12,14),(16,17)) ?
Ещё не проснулась :(
11 май 06, 11:57    [2651612]     Ответить | Цитировать Сообщить модератору
 Re: Задачка интересная  [new]
orawish
Member

Откуда: Гадюкино-2 (City)
Сообщений: 15487
Вот вариантец, чисто в лоб - по производительности просядет - к гадалке не ходить, ну, как подход..
with t 
  as (
     select  10 as b, 20 as e from dual union all
     select  12 as b, 15 as e from dual union all
     select  35 as b, 40 as e from dual
     ) 
select e,b from t
minus select e,b from t 
  where level > 1
  connect by (prior b <= b and prior e >  e )
          or (prior b <  b and prior e >= e ) 
11 май 06, 12:36    [2651893]     Ответить | Цитировать Сообщить модератору
Все форумы / Oracle Ответить