One Dimensional Kingdoms | CodeChef Solution

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

Task

N one dimensional kingdoms are represented as intervals of the form [a_i , b_i] 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 a_i and b_i.

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 ≤ a_i ≤ b_i ≤500
Subtask 2 (30 points) : 1 ≤ T ≤ 100 , 1 ≤ N ≤ 1000 , 0 ≤ a_i ≤ b_i ≤ 1000
Subtask 3 (50 points) : 1 ≤ T ≤ 20 , 1 ≤ N ≤ 10⁵, 0 ≤ a_i ≤ b_i ≤ 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[0].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[0][1]
    
    for kd in kds[1:]:
        if (kd[0] > end):
            bombs += 1
            end = kd[1]
        else:
            end = min(end, kd[1])
    
    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[0])
    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();
                lst.add(new kingdoms(a,b));
            }
            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.