First, let us ignore the nonnegativity constraint on the approximating polynomial.
By linear transformation of the variable, one may suppose that $I_{0}=[-A,-1]$ and
$I_{1}=[1,B]$ and by a linear transformation on the approximating polynomial $P_{n}$, one may suppose that $y_{0}=-1$ and $y_{1}=1$ (since $y_{0}\neq y_{1}$). Now, by Chebyshev's theorem, a best polynomial approximant $P_{n}(x)$ to $\text{sgn}(x)$ on $I=I_{0}\cup I_{1}$ exists and is unique.
It has been proved in [1] that
$$C_{1}n^{-1/2}e^{-\eta n}\leq\|P_{n}-\text{sgn}\|_{I,\infty}=\inf_{p\in\mathcal{P}_{n}}\|p-\text{sgn}\|_{I,\infty}
\leq C_{2}n^{-1/2}e^{-\eta n},$$
where $C_{1}$ and $C_{2}$ are positive constants depending on $A$ and $B$, and $\eta$ is the critical value of the Green's function of the region $\mathbb{C}\setminus I$ with pole at infinity
(Ref. [1] seems difficult to find on the internet, but the above result is mentioned in Ref. [2] which is more accessible).
By the above inequality, one gets that, indeed, an $\epsilon$-approximation is achieved by a polynomial of degree $O(\log(1/\epsilon))$.
Concerning the nonnegativity constraint, obviously, it cannot be satisfied by odd approximating polynomials.
For even degree $n$, it follows from the discussion on p.295 of [2] that the best approximant $P_{n}$ has at least $n-2$ critical points $x_{j}$, $j=1,\ldots,n-2$, which lie in $I$ and are alternating points for the error function, that is $|(P_{n}-\text{sign})(x_{j})|=\epsilon$. Hence, there is at most one critical point which is not an alternating point. This point is shown to belong to $\mathbb{R}\setminus[-A,B]$, and the corresponding critical value could, a priori, contradicts the nonnegativity constraint.
References
[1] W.H.J. Fuchs, On the degree of Chebyshev approximation on sets with several components, Izv. Akad. Nauk Armyan. SSR Ser. Mat. 13 (1978), 396-404, 541.
[2] A. Eremenko, P. Yuditskii, Polynomials of the best uniform approximation to sgn(x) on two intervals, J. Anal. Math. 114 (2011), 285-315.
