Finding smallest cube in $\mathbb R^n$ that contains intersection between two regions

I don't think this is a pure math problem, so I post it here.

Assume we have two regions in $\mathbb R^n$: $$\lbrace x : a \leq x \leq b \rbrace\\$$ and $$\left\lbrace x : \sum_{i=1}^n |x_i | \leq c \right\rbrace$$

The problem is to find the smallest possible cube that contains the intersection between the two regions.

If $x \in \mathbb R^2$, then the first region is a square and the second a diamond-shape, and the problem looks something like this (the red square is the solution to the problem): The problem is reasonably easy if one takes a particular case like the one on the picture. We can find the equation for the line that crosses the square and find the $x$ and $y$ values where the line is equal to the constants signifying the sides of the square. However, which sides of the square we use depends on the position of the square (it can even be crossed by several lines). In general, it seems to be a lot of special cases to deal with by going that route.

I am wondering if there are general procedures that can be applied to this problem, or if anyone knows an elegant solution to this particular one.