One Dimensional Kingdoms
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
N one dimensional kingdoms are represented as intervals of the form [ai , bi] on the real line. A kingdom of the form [L, R] can be destroyed completely by placing a bomb at a point x on the real line if L ≤ x ≤ R.
Your task is to determine minimum number of bombs required to destroy all the one dimensional kingdoms.
- First line of the input contains T denoting number of test cases.
For each test case, first line contains N denoting the number of one dimensional kingdoms.
- For each next N lines, each line contains two space separated integers ai and bi.
For each test case , output an integer denoting the minimum number of bombs required.
Subtask 1 (20 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 100 , 0 ≤ ai ≤ bi ≤500
Subtask 2 (30 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 1000 , 0 ≤ ai ≤ bi ≤ 1000
Subtask 3 (50 points) : 1 ≤ T ≤ 20 , 1 ≤ N ≤ 105, 0 ≤ ai ≤ bi ≤ 2000
Input: 1 3 1 3 2 5 6 9 Output: 2
ExplanationThere are three kingdoms [1,3] ,[2,5] and [6,9]. You will need at least 2 bombs to destroy the kingdoms. In one of the possible solutions, you can place two bombs at x = 2 and x = 6 .
|Tags||easy-medium, greedy, jan15, nssprogrammer|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, 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, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.