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\%~, 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)~