# Binary string satisfying several constraints

I’m trying to solve this problem, but without success.

Problem: You’re given a binary string where some of the bits are replaced by `?`. You’re also given several intervals [$$l_i$$, $$r_i$$] ($$l_i < r_i$$). Find a binary string S with `?` replaced by `0` or `1`, such that in each interval [$$l$$, $$r$$], s[$$l..r$$] includes both `0` and `1`.

Example:

Given the string `00?11` and the interval [2, 3], the string `00111` satisfies the requirements, as S[2..3]=`01` include both 0 and 1.

However, the string `00?11` and the intervals [2, 3] and [3, 4] cannot be solved, as the `?` would have to be both `0` and `1`.

The bounds are |S|,Q<=1e5

I tried using greedy, but it’s giving wrong answer for this case: `0??0`, [1, 3], [2, 3] and [3, 4], as the greedy algorithm would try `0??0` -> `01?0` -> `0100` -> fail, yet there exists a solution (`0010`).

I tried removing completely overlapping intervals (such as [1, 3] and [2, 3]), but there’re other cases I found that fails. What would be a correct solution?

Thanks.