Maximally extend integer intervals

Question

Suppose you are given a set of non-intersecting intervals of integers [a1,b1],[a2,b2],[a3,b3],...,[aN,bN]. (Where [a,b] is the set of integers greater than or equal to a and less than or equal to b.)

The interval at index X covers bX - aX + 1 values. We'll call this number cX.

Given that each interval can either be...

• unchanged (stays as [aX,bX]),
• extended to the right towards the + side of number the line by cX (becoming [aX,bX + cX]),
• or extended to the left towards the - side of number the line by cX (becoming [aX - cX,bX]),

what is the maximum number of values that can be covered by the union of all the updated intervals, given that they are still all non-intersecting?

Write a function or program that takes a string of the form [a1,b1],[a2,b2],[a3,b3],...,[aN,bN] and computes this maximum. If writing a function, return the value. If writing a full program, use stdin for input and print the value to stdout (or use closest alternatives).

You may assume all values are well within normal signed 32-bit integer limits and that aX is less than or equal to bX for all indices X. The intervals may be in any order, they are not necessarily always increasing. They must be given as a string in the format above. The string may be empty, in which case the answer will be 0.

The shortest submission in bytes wins.

Example

If the input were [-3,0],[1,2],[4,9] the output would be 22. The middle interval has no room to expand either way so it must remain unchanged. The left and right intervals can both be extended to [-7,0] and [4,15] respectively. The union of [-7,0] and [1,2] and [4,15] contains all the values from -7 to 15, except 3. That's 22 values.

Answer 1

Haskell, 145 bytes

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.('[':).(++"]")

Sample runs:

λ: x ""
0

λ: x "[5,6]"
4

λ: x "[-3,0],[1,2],[4,9]"
22

Answer 2

R, 282 278 269 247

This got big really quickly dealing with the string input. I suspect I can golf this better, but have run out of time at the moment.

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)}

Essentially the idea is

• Take in the string and turn it into a 2 row matrix
• Make sure it is in the right order
• Work out the differences for each column
• Double the first and last differences
• Double the middle differences if they have a gap to the previous or next that is large enough
• Return the sum of the differences

Edit: realized I miscounted the chars originally, then rearranged a few things to shave a few.