Chefina and Ranges

All submissions for this problem are available.
### Read problem statements in [Hindi](http://www.codechef.com/download/translated/DEC19/hindi/CHFRAN.pdf), [Bengali](http://www.codechef.com/download/translated/DEC19/bengali/CHFRAN.pdf), [Mandarin Chinese](http://www.codechef.com/download/translated/DEC19/mandarin/CHFRAN.pdf), [Russian](http://www.codechef.com/download/translated/DEC19/russian/CHFRAN.pdf), and [Vietnamese](http://www.codechef.com/download/translated/DEC19/vietnamese/CHFRAN.pdf) as well. Chefina is playing with ranges. There are $N$ ranges $[l_1, r_1], [l_2, r_2], \ldots, [l_N, r_N]$. Chefina wants to divide the ranges into two nonempty subsets in such a way that each range is in exactly one subset and whenever two ranges have a common point, they are in the same subset. Since this could be difficult to achieve, Chefina can delete any number of ranges (possibly zero) and then divide the remaining ranges into such nonempty subsets. She wants to know whether it is possible to achieve her task after deleting some ranges and if it is possible, she also wants to know the minimum number of ranges she needs to delete to achieve it. ### Input  The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.  The first line of each test case contains a single integer $N$.  $N$ lines follow. For each $i$ ($1 \le i \le N$), the $i$th of these lines contains two spaceseparated integers $l_i$ and $r_i$. ### Output For each test case, print a single line containing one integer ― the minimum number of ranges to delete, or $1$ if it is impossible to delete some ranges and divide the remaining ranges into two nonempty subsets. ### Constraints  $1 \le T \le 10$  $1 \le N \le 10^5$  $1 \le l_i \le r_i \le 10^9$ for each valid $i$ ### Subtasks **Subtask #1 (10 points):** $N = 16$ **Subtask #2 (15 points):** $N = 1,000$ **Subtask #3 (15 points):** $r_i \le 10^6$ for each valid $i$ **Subtask #4 (60 points):** original constraints ### Example Input ``` 3 3 1 4 2 6 5 7 2 1 4 4 6 2 3 7 8 9 ``` ### Example Output ``` 1 1 0 ``` ### Explanation **Example case 1:** It is enough to delete the range $[2, 6]$. **Example case 2:** There is no way to divide these two ranges into two suitable nonempty subsets and deleting any range obviously makes it impossible too. **Example case 3:** There is no need to delete any ranges, we can just put one range into one subset and the other range into the other subset.Author:  rishup_nitdgp 
Editorial  https://discuss.codechef.com/problems/CHFRAN 
Tags  dec19, easymedium, greedy, melfice, partitioning, rishup_nitdgp 
Date Added:  28042019 
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