One King Solution
Difference between en3 and en4, changed 4 character(s)
### PROBLEM LINK:↵
[ONEKING](http://www.codechef.com/problems/ONEKING)↵
 ↵
### DIFFICULTY:↵
EASY-MEDIUM↵
 ↵
### PROBLEM:↵
Given **N (≤100000)** intervals **[ $A_i$ , $B_i$ ]**, one such interval can be deleted by placing a bomb at x if $A_i$ ≤ x ≤ $B_i$. Find minimum number of bombs required to delete all intervals.↵

### EXPLANATION:↵
In this problem we can minimize the number of bombs by dropping the bombs at intersection points. So we have to divide the intervals into disjoint sets such that each set consists of intervals having a common intersection point.↵

Example: (1,5) , (4,5) , (2,3) , (3,4) , (4,4) , (6,8)↵

We can divide the following intervals into  ↵
{(1,5) , (4,5)}  ↵
{(2,3) , (3,4) , (4,4)}  ↵
{(6,8)}↵

For each set 1 bomb is required i.e Number of such sets = Number of minimum bombs↵

#### How can we find a set of intervals having a common intersection point?↵

1. Arrange the intervals according to the increasing order of lower bounds of intervals.↵

2. Let the sequence be : ( $a_1$ , $b_1$ ) , ( $a_2$ , $b_2$ ) , ( $a_3$ , $b_3$ ) , ( $a_4$ , $b_4$ ) , . . . , ( $a_n$ , $b_n$ )↵

3. We will check if ( $a_1$ , $b_1$ ) , ( $a_2$ , $b_2$ ) intersects.↵

if $a_2$ < $b_1$ then ( $a_1$ , $b_1$ ) and ( $a_2$ , $b_2$ ) intersects and↵
intersection interval will be = ( $a_2$ , min( $b_1$ , $b_2$ ) )↵
   ↵
    lets say (x,y) = ( $a_2$ , min( $b_1$ , $b_2$ ) )↵

4. Now consider ( $a_3$ , $b_3$ ).It will intersect ( $a_1$ , $b_1$ ) and ( $a_2$ , $b_2$ ) if and only if ( $a_3$ , $b_3$ ) intersects (x,y) i.e if ( $a_3$ , $b_3$ ) intersects the intersection interval of ( $a_1$ , $b_1$ ) and ( $a_2$ , $b_2$ ).Again if $a_3$ < y then (x,y) and ( $a_3$ , $b_3$ ) intersects and we will modify (x,y) as   ↵
**(x,y) = ( $a_3$ , min( $b_3$ , y ) )**↵
   ↵
5. We will continue until we find (x,y) has no intersection with interval ( $a_i$ , $b_i$ ).↵
   So the set {( $a_1$ , $b_1$ ),( $a_2$ , $b_2$ ),...,( $a_{i-1}$ , $b_{i-1}$ )} has a common intersection point and interval (x,y) is     common to all the intervals in the set. We can place a bomb at any point in (x,y) to destroy all    the intervals in the set.↵

6. Continue the procedure now starting with ( $a_i$ , $b_i$ ).↵

Pseudo code:↵

~~~~~↵
n = number of intervals↵
pairs = array of intervals↵

n,pairs=input↵

sort(pairs,pairs+n)↵

count=1 //minimum number of bombs = 1↵
test_pair=pairs[0]↵

for j = 1 to n:↵
    if pairs[j].lower_bound <= test_pair.upper_bound :↵
test_pair.lower_bound = pairs[j].lower_bound↵
test_pair.upper_bound = min(pairs[j].upper_bound,test_pair.upper_bound)↵
    ↵
    else:↵
count++↵
test_pair = pairs[j]↵

print count↵
~~~~~↵

Complexity: **O(N
logN).**↵

### SOLUTIONS:↵
[solution](https://pastebin.com/q9ZikK1k)↵






History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English jarvisnaharoy 2019-06-13 19:39:16 4 Tiny change: 'ity: **O(N).**\n\n#' -> 'ity: **O(NlogN).**\n\n#'
en3 English jarvisnaharoy 2019-06-13 15:30:51 2 Tiny change: '{(1,5) , (5,5)} \n{(' -> '{(1,5) , (4,5)} \n{('
en2 English jarvisnaharoy 2019-06-13 14:47:33 443 (published)
en1 English jarvisnaharoy 2019-06-13 08:52:22 2529 Initial revision (saved to drafts)