Coloring Intervals

All submissions for this problem are available.
You are given $n$ intervals on the $X$ axis. Each interval $i$ is specified by its ends $[L_i, R_i]$. You want to color each interval either blue or yellow. After coloring all the intervals, the $X$ axis will will have $4$ colors:  White, the part of $X$ axis contained in no interval  Blue, the part of $X$ axis contained in atleast one blue colored interval and no yellow colored interval.  Yellow, the part of $X$ axis contained in atleast one yellow colored interval and no blue colored interval.  Green, the part of $X$ axis contained in at least one blue colored interval and at least one yellow colored interval. You want to color the intervals so that the total length of the part colored green is maximized. If there are multiple ways to color which maximize the green part, you can output any of them. ###Input:  First line will contain $T$, number of testcases. Then the testcases follow.  The first line of each testcase contains $n$, the number of intervals.  The $i^{\text{th}}$ of the next $n$ lines contains two integers $L_i$ and $R_i$ describing the $i^{\text{th}}$ interval. ###Output: For each testcase, output a single string on a new line, whose $i^{\text{th}}$ character is $0$ if you color the $i^{\text{th}}$ interval blue, and $1$ if you color it yellow. ###Constraints  $ 1 \leq T \leq 10^5 $  $ 1 \leq n \leq 10^5 $  The sum of $n$ over all testcases doesn't exceed $10^5$.  $ 1 \leq L_i \leq R_i \leq 10^9 $ for al $ 1 \leq i \leq n$. ###Sample Input: 1 3 3 7 2 5 6 9 ###Sample Output: 100 ###Explanation: The intervals are $[3, 7]$, $[2, 5]$, $[6, 9]$. It is optimal to color them in yellow, blue and blue respectively. In this coloring:  $[2, 3) \cup (7, 9]$ is colored blue.  $(5, 6)$ is colored yellow.  $[3, 5] \cup [6, 7]$ is colored green, with a total length of $(5  3) + (7  6) = 3$.  Rest of the $X$ axis is colored white. Please note that colors at the endpoints of the intervals don't matter when computing the lengths, and we can ignore them. Open and closed intervals have been used in the explanation section only for clarity, and it doesn't matter whether they are open or closed. Note that `011` is also a valid output.Author:  jtnydv25 
Tags  jtnydv25 
Date Added:  13122019 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, SQL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, R, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 