Feasibility of equations with max constraints
Let $y_i=\min\{b_k| i\in J_k\}$. Observe for any feasible solution, $x_i\leq y_i$.

Claim: The system of $\max$ equations is feasible iff $x_i=y_i$ for $1\leq i\leq n$ is a solution.

Proof. 
If $x_i=y_i$ is a solution, then the system of $\max$ equations is feasible

Consider any solution, and $x_i &lt; y_i$ for some $i$. We can increase $x_i$ to $y_i$ without violate any equation. Assume it violates the $k$th equation, namely $\max\{x_j|j,i\in J_k\}=b_k$, then it implies $y_i = \max\{x_j|j,i\in J_k\} &gt; b_k$, but that's a contradiction because
$$
b_k \geq \min\{b_j| i\in J_j\} = y_i = \max\{x_j|j,i\in J_k\} &gt; b_k
$$.

The algorithm is just compute $y_i$s and check if it satisfies all the equations. This takes linear time.