Найти пересечение 2 множеств в объединенной нотации

Учитывая два набора действительных чисел, описанных как объединение интервалов, выведите описание пересечения этих двух наборов как объединение интервалов одного типа.

Входные наборы всегда будут состоять из объединений интервалов, так что каждый интервал начинается и заканчивается с другим целым числом (т. Е. Ни один интервал не имеет меры ноль). Однако разные интервалы в одном и том же наборе могут начинаться или заканчиваться в одном и том же целом числе или совпадать.

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

Ввод может принимать любую форму, которая подходит для вашего языка по вашему выбору, если он состоит из двух списков пар целых чисел.

Например, вы можете представить набор как:

[-10,-4]u[1,5]u[19,20]

Или как:

[[-10,-4],[1,5],[19,20]]

Или как:

[-10,-4;1,5;19,20]

Ваше выходное представление должно быть идентично вашему входному представлению (за исключением того, что это только один список интервалов вместо двух).

Примеры / Тестовые случаи:

Входные данные:

[[[-90,-4],[4,90]],[[-50,50]]]

Вывод:

[[-50,-4],[4,50]]

Другими словами, мы пересекаем множество, которое содержит все действительные числа от -90 до -4 и все действительные числа от 4 до 90 с множеством, которое содержит все действительные числа от -50 до 50. Пересечение - это множество, содержащее все действительные числа от -50 до -4 и все действительные числа от 4 до 50. Более наглядное объяснение:

-90~~~~~-4  4~~~~~90   intersected with
    -50~~~~~~~~50        yields:
    -50~-4  4~~50

Входные данные:

"[-2,0]u[2,4]u[6,8]
[-1,1]u[3,5]u[5,9]"

Вывод:

"[-1,0]u[3,4]u[6,8]"

Входные данные:

[-9,-8;-8,0;-7,-6;-5,-4]
[-7,-5;-1,0;-8,-1]

Вывод:

[-8,0]

Неверный вывод (даже если он представляет один и тот же набор):

[-8,0;-7,-5;-5,0]

Подсчет очков:

Это код-гольф, поэтому выигрывает самый короткий источник в байтах, который может быть изменен следующим бонусом.

Бонус:

-15%, если вы также поддерживаете положительную и отрицательную бесконечность в качестве границ интервалов. Вы можете выбрать, какие токены представляют эти числа. (И да, бесконечность - это число в гиперреалах; P)

Mathematica, 41 байт - 15% = 34,85

Mathematica имеет встроенную функцию для пересечения интервалов.

List@@IntervalIntersection@@Interval@@@#&

Пример:

In[1]:= List@@IntervalIntersection@@Interval@@@#&[{{{-90, -4}, {4, Infinity}}, {{-50,Infinity}}}]

Out[1]= {{-50, -4}, {4, Infinity}}

Haskell, 145 байт

import Data.List
q(a,b)=[a,a+0.5..b]
p@(a,b)%(h:t)|h==b+0.5=(a,h)%t|1<2=p:(h,h)%t
p%_=[p]
a#b|h:t<-nub$sort$intersect(q=<<a)$q=<<b=(h,h)%t|1<2=[]

Пример использования: [(-2.0,0.0),(2.0,4.0),(5.0,6.0),(6.0,8.0)] # [(-1.0,1.0),(3.0,5.0),(5.0,9.0)]-> [(-1.0,0.0),(3.0,4.0),(5.0,8.0)].

Как это работает:

                 q=<<a            -- turn each pair in the 1st input list into
                                  -- lists with halves in between (e.g. (1,4) ->
                                  -- [1,1.5,2,2.5,3,3.5,4]) and concatenate them
                                  -- to a single list
                      q=<<b       -- same for the second input list
    nub$sort$intersect            -- sort the intersection of those lists
                                  -- and remove duplicates
h:t<-                             -- call the first element h and the rest t
                       (h,h)%t    -- start rebuilding the intervals
                          |1<2=[] -- if there's no first element h, one of the
                                  -- input lists is empty, so the output is also
                                  -- empty


p@(a,b)%(h:t)                     -- an interval p = (a,b), build from a list (h:t)
             =(a,h)%t             -- becomes (a,h)
      |h==b+1                     --   if h equals b+0.5
                    p:(h,h)%t     -- or is put in the output list, followed by
                                  --       a new interval starting with (h,h)
      |1<2                        --   otherwise
p%_=[p]                           -- base case of the interval rebuilding function 

Я ставлю «половинку» -значение x.5в списке, потому что мне нужно отличать (1,2),(3,4)от (1,4). Внешне x.5оба стали бы [1,2,3,4], но с x.5первым становится [1,1.5,2,3,3.5,4](чего не хватает 2.5) и вторым [1,1.5,2,2.5,3,3.5,4].

Рубин, 90 байт

Сопоставляет каждый из двух наборов с плоским массивом, получает пересечение наборов этих массивов, затем разбивает результат на непрерывные куски и отображает каждый кусочек в первый и последний элемент. Очень просто.

->s{a,b=s.map{|y|y.flat_map{|f,l|[*f..l]}.sort}
(a&b).slice_when{|a,b|b-a>1}.map &:minmax}

Применение:

f=->s{a,b=s.map{|y|y.flat_map{|f,l|[*f..l]}.sort}
(a&b).slice_when{|a,b|b-a>1}.map &:minmax}

s = [[[-90,-4],[4,90]], [[-50,50]]]
p f[s] # => [[-50, -4], [4, 50]]

s = [[[-2,0],[2,4],[6,8]], [[-1,1],[3,5],[5,9]]]
p f[s] # => [[-1, 0], [3, 4], [6, 8]]

s = [[[-9,-8],[-8,0],[-7,-6],[-5,-4]],[[-7,-5],[-1,0],[-8,-1]]]
p f[s] # => [[-8, 0]]