Let $D$ be the minimum distance between $x$'s (merging all the $x$'s into one list).

Let $k$ be an integer $\ge \max(16\log(8/D^2),10N)\ /\ D^2$.

Then a polynomial of degree of $6(k+1)(n-1)$ suffices.

Proof: Let $p(x) = \frac{1}{2}(3 q(x) - q^3(x))$, where $q(x) = \sum_i \pm \Pi_{j \neq i} r_{ij}(x)$ and

$$r_{ij}(x) = \left(1-\frac{(x-x_i)^2}{4}\right)^k \frac{(x-x_j)^2}{(x_i-x_j)^2}$$

Then $p$ is clearly of the specified degree, and has the specified values at the $x_i$'s.

The key is to show that $p$ is bounded by $\pm1$.

Small terms: When $|x-x_i| > D/2$, $r_{ij}(x) \le (1-D^2/16)^k (4/D^2) < %(1-D^2/16)^{\large(16/D^2)\log(8/D^2)}(4/D^2) < 1/2$, so $\Pi_{j \neq i} r_{ij}(x) < 2^{-(n-1)}$.

Large terms: When $|x-x_i| < D/2$,

$$r_{ij}(x) \le \left(1-\frac{(x-x_i)^2}{4}\right)^k \left(1 - \frac{x-x_i}{x_j-x_i}\right)^2 \le \left(1-\frac{(x-x_i)^2}{4}\right)^k \left(1 + \frac{2|x-x_i|}{kD}\right)^k $$ $$ \le \left(1+ \frac{2|x-x_i|}{kD}-\frac{(x-x_i)^2}{4}\right)^k \le \left(1+\frac{4}{k^2D^2}\right)^k \le e^{\large 4/D^2k} \le e^{\large 4/10N} \le (3/2)^{\large 1/N}. $$ So $\Pi_{j \neq i} r_{ij}(x) < 3/2$

Since each $x$ is within $D/2$ of at most one $x_i$, $q(x)$ is the sum of at most one large term bounded by 3/2, and by $n-1$ small terms bounded by $2^{-(n-1)}$. So $|q|\le2$, and $|p|\le1$.

Let $D$ be the minimum distance between $x$'s, merging all the $x$'s into one list of length $N$.

Let $k$ be an integer $\ge \max(16\log(8/D^2),10N)\ /\ D^2$.

Then a polynomial of degree of $6(k+1)(N-1)$ suffices.

Proof: Let $p(x) = \frac{1}{2}(3 q(x) - q^3(x))$, where $q(x) = \sum_i \pm \Pi_{j \neq i} r_{ij}(x)$ and

$$r_{ij}(x) = \left(1-\frac{(x-x_i)^2}{4}\right)^k \frac{(x-x_j)^2}{(x_i-x_j)^2}$$

Then $p$ is clearly of the specified degree, and has the specified values at the $x_i$'s.

The key is to show that $p$ is bounded by $\pm1$.

Small terms: When $|x-x_i| > D/2$, $r_{ij}(x) \le (1-D^2/16)^k (4/D^2) < %(1-D^2/16)^{\large(16/D^2)\log(8/D^2)}(4/D^2) < 1/2$, so $\Pi_{j \neq i} r_{ij}(x) < 2^{-(N-1)}$.

Large terms: When $|x-x_i| < D/2$,

$$r_{ij}(x) \le \left(1-\frac{(x-x_i)^2}{4}\right)^k \left(1 - \frac{x-x_i}{x_j-x_i}\right)^2 \le \left(1-\frac{(x-x_i)^2}{4}\right)^k \left(1 + \frac{2|x-x_i|}{kD}\right)^k $$ $$ \le \left(1+ \frac{2|x-x_i|}{kD}-\frac{(x-x_i)^2}{4}\right)^k \le \left(1+\frac{4}{k^2D^2}\right)^k \le e^{\large 4/D^2k} \le e^{\large 4/10N} \le (3/2)^{\large 1/N}. $$ So $\Pi_{j \neq i} r_{ij}(x) < 3/2$

Since each $x$ is within $D/2$ of at most one $x_i$, $q(x)$ is the sum of at most one large term bounded by 3/2, and by $N-1$ small terms bounded by $2^{-(N-1)}$. So $|q|\le2$, and $|p|\le1$.