Максимально расширить целочисленные интервалы

14

Предположим, вам дан набор непересекающихся интервалов целых чисел [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]. (Где [a,b]множество целых чисел больше или равно aи меньше или равно b.)

Интервал в индексе Xохватывает bX - aX + 1значения. Мы позвоним по этому номеру cX.

Учитывая, что каждый интервал может быть ...

  • без изменений (остается как [aX,bX]),
  • продлен вправо в +сторону от номера строки cX(становясь [aX,bX + cX]),
  • или продлен влево к -стороне номера линии cX(становясь [aX - cX,bX]),

Каково максимальное количество значений, которое может быть покрыто объединением всех обновленных интервалов, учитывая, что они все еще не пересекаются?

Напишите функцию или программу, которая принимает строку в форме [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]и вычисляет этот максимум. Если вы пишете функцию, верните значение. Если вы пишете полную программу, используйте stdin для ввода и выведите значение в stdout (или используйте самые близкие альтернативы).

Вы можете предположить, что все значения находятся в пределах нормальных 32-разрядных целочисленных пределов со знаком, и это aXменьше или равно bXдля всех индексов X. Интервалы могут быть в любом порядке, они не обязательно всегда увеличиваются. Они должны быть представлены в виде строки в формате выше. Строка может быть пустой, и в этом случае ответ будет 0.

Самая короткая подача в байтах побеждает.

пример

Если бы вход был [-3,0],[1,2],[4,9]выходным, было бы 22. Средний интервал не имеет места для расширения в любом случае, поэтому он должен оставаться неизменным. Левый и правый интервалы могут быть увеличены до [-7,0]и [4,15]соответственно. Объединение [-7,0]и [1,2]и [4,15]содержит все значения от -7 до 15, кроме 3. Это 22 значения.

code-golf set-theory Кальвин Хобби
источник
3
Можем ли мы использовать для ввода исходное строковое представление массивов нашего языка, или оно должно быть именно этого формата?
Мартин Эндер
@ MartinBüttner Нет. Вам нужно использовать именно этот формат. (Я знаю, что это обоюдоострый меч, но так оно и есть.)
Увлечения Кэлвина
Можете ли вы расширить данный интервал с обеих сторон? Например, может [5,6]стать [3,8](для ответа 6), или это может быть просто [5,8]или [3,6](для ответа 4)?
MtnViewMark
@MtnViewMark Нет. Они могут быть расширены только с одной стороны (или вообще не могут быть)
Увлечения Кэлвина

Ответы:

4

Haskell, 145 байт

import Data.List
x=maximum.map length.filter(nub>>=(==)).map concat.sequence.map(\[a,b]->[[2*a-b-1..b],[a..b],[a..2*b-a+1]]).read.('[':).(++"]")

Образцы прогонов:

λ: x ""
0

λ: x "[5,6]"
4

λ: x "[-3,0],[1,2],[4,9]"
22
MtnViewMark
источник
1

R 282 278 269 247

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

f=function(s){i=matrix(strtoi(strsplit(gsub('[^0-9,-]','',s),',')[[1]]),nrow=2);l=0;if((a<-length(b<-order(i[1,])))>0){if(a>1)i=i[,b];l=diff(i[,1:a])+1;x=c(t(i));for(n in 1:a)if(n==1|n==a|x[n]-l[n]>x[n+a-1]|x[n+a]+l[n]<x[n+1])l[n]=l[n]*2;};sum(l)}

По сути идея

  • Возьмите строку и превратите ее в матрицу из 2 строк.
  • Убедитесь, что это в правильном порядке
  • Определите различия для каждого столбца
  • Удвойте первое и последнее отличие
  • Удвойте средние различия, если они имеют разрыв с предыдущим или следующим, который является достаточно большим
  • Вернуть сумму разниц

Редактировать: понял, что я неправильно подсчитал символы, а затем перестроил несколько вещей, чтобы побрить несколько.

MickyT
источник