# One Dimensional Kingdoms | CodeChef Solution

Hello coders, today we are going to solve One Dimensional Kingdoms CodeChef Solution whose Problem Code is ONEKING.

Contents

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.

## Input Format

• 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.

## Output Format

For each test case , output an integer denoting the minimum number of bombs required.

## Constraints

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

Example

Sample Input

``````1
3
1 3
2 5
6 9
``````

Sample Output

``2``

Explanation

There 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 .

## Solution – One Dimensional Kingdoms

### C++

```#include <bits/stdc++.h>
using namespace std;
bool com(pair<int,int> &a,pair<int,int> &b)
{
return a.second < b.second;
}
int main()
{
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<pair<int,int>> k;
int a,b;
for(int i=0;i<n;i++)
{
cin>>a>>b;
k.push_back(make_pair(a,b));
}
sort(k.begin(),k.end(),com);
int bombs=1;
int boundary=k.second;
for(int i=1;i<n;i++)
{
if(boundary<k[i].first)
{
bombs+=1;
boundary= k[i].second;
}
}
cout<<bombs<<endl;
}
return 0;
}```

### Python

```def minBombs(kds):
bombs = 0
end = kds

for kd in kds[1:]:
if (kd > end):
bombs += 1
end = kd
else:
end = min(end, kd)

bombs += 1
return bombs

T = int(input())
for t in range(T):
N = int(input())
kds = []
for n in range(N):
a, b = map(int, input().split())
kds.append([a, b])

kds.sort(key=lambda kd: kd)
print(minBombs(kds))```

### Java

```/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{public static void main (String[] args) throws java.lang.Exception
{
Scanner s = new Scanner(System.in);
int t = s.nextInt();
while(t-- != 0){
int n = s.nextInt();
ArrayList<kingdoms> lst = new ArrayList<>();
for(int i = 0; i < n; ++ i){
int a = s.nextInt();
int b = s.nextInt();
}
Collections.sort(lst);

int end = lst.get(0).end;
int bomb = 1;
for (int i = 1; i < lst.size(); i++) {
if(lst.get(i).start <= end){
continue;
}else {
bomb++;
end = lst.get(i).end;
}
}
System.out.println(bomb);
}
}
static class kingdoms implements Comparable<kingdoms>{
int start;
int end;
kingdoms(int start, int end){
this.start = start;
this.end = end;
}

@Override
public int compareTo(kingdoms obj){
return this.end-obj.end;
}
}
}

```

Disclaimer: The above Problem (One Dimensional Kingdoms) is generated by CodeChef but the Solution is Provided by CodingBroz. This tutorial is only for Educational and Learning Purpose.