Suppose you are given a set of non-intersecting intervals of integers
[a,b] is the set of integers greater than or equal to
a and less than or equal to
The interval at index
bX - aX + 1 values. We'll call this number
Given that each interval can either be...
- unchanged (stays as
- extended to the right towards the
+side of number the line by
[aX,bX + cX]),
- or extended to the left towards the
-side of number the line by
[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.
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
[4,15] respectively. The union of
[4,15] contains all the values from -7 to 15, except 3. That's 22 values.