Note that if $X=max(r_i-l_i+1)$, then we need exactly $X$ distinct bands.

An example of an ordering that is valid is $1,2,3,\dots ,X,1,2,3,\dots$.

Let $A$ be the plan that we output. For the remaining $50\mathrm{\%}$, we must maximize the number of indices $j$ $(2\le j\le N)$ where $A_j=A_{j-1}$. Let's call $j$ good if we can do this. First, let's define $f_j$ as the minimal $l_i$ such that $l_i\le j\le r_i$. If there is no $i$ such that $l_i\le j\le r_i$, then $f_j=j$. Observe that $j$ is good if and only if $f_j=j$. This is because if $f_j<j$ there exists some $i$ such that $l_i\le j-1<j\le r_i$. So, if we make $A_j=A_{j-1}$, then there will be $2$ identical bands playing within some $[l_i,r_i]$. On the other hand, if $f_j=j$, there clearly exists no $i$ where $j$ and $j-1$ are in $[l_i,r_i]$. Initially, set $A_1=1$. Then, for each $j$ $(2\le j\le N)$, $A_j=A_{j-1}$ if $f_j=j$. Otherwise, $A_j=A_{j-1}+1$, making sure that if $A_j=X+1$ we set it to $1$.

Time Complexity: $\mathcal{O}(N)$