HackerRank Mr. X and His Shots problem solution

In this HackerRank Mr. X and His Shots problem, we have given the cricketer, and his favorite shots, and the range of players. we need to find the strength of each player so that a player can stop the shot.

Problem solution in Python programming.

from bisect import bisect_left, bisect_right, insort_left
n, m = map(int, input().split(" "))

start_values = {}
end_values = {}

for _ in range(n):
    start, end = map(int,input().split(" "))
    if start in start_values:
        start_values[start] += 1
    else:
        start_values[start] = 1

    if end in end_values:
        end_values[end] -= 1
    else:
        end_values[end] = -1
        
start_keys = []
end_keys = []

temp = 0
for el in sorted(start_values.keys()):
    temp += start_values[el]
    start_values[el] = temp
    start_keys.append(el)
    
temp = 0
for el in sorted(end_values.keys()):
    temp += end_values[el]
    end_values[el] = temp
    end_keys.append(el)

result = 0


for _ in range(m):
    start, end = map(int,input().split(" "))
    if start > end_keys[-1] or end < start_keys[0]:
        continue
        
    temp_result = 0
    if not end in start_values:
        i = bisect_left(start_keys, end+1) - 1
        start_values[end] = start_values[start_keys[i]]
    temp_result += start_values[end]

    i = bisect_left(end_keys, start) -1
    if i >= 0: 
        temp_result += end_values[end_keys[i]]

    result += temp_result
print (result)

Problem solution in Java Programming.

import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;

class Range{
    int low;
    int high;
    
    public Range(int low,int high){
        this.low=low;
        this.high=high;
    }
    
    public static boolean isOverlapping(Range a,Range b){
        if(a.high <b.low || a.low >b.high)
            return false;
        else 
            return true;
    }
}
class RangeComparator implements Comparator<Range>{
 
	@Override
	public int compare(Range a,Range b) {
		if(a.low < b.low)
            return -1;
        else if(a.low>b.low)
            return 1;
        else
            return a.high-b.high;
	}
}

public class Solution {

    public static void main(String[] args) {
        /* Enter your code here. Read input from STDIN. Print output to STDOUT. Your class should be named Solution. */
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int m=in.nextInt();
        Range shotArray[]=new Range[n];
        Range fieldArray[]=new Range[m];
        int count=0;
        int total=0;
        
       for(int i=0;i<n;i++)
          shotArray[i]=new Range(in.nextInt(),in.nextInt());

        for(int i=0;i<m;i++)
            fieldArray[i]=new Range(in.nextInt(),in.nextInt());

        Arrays.sort(shotArray,new RangeComparator());
        Arrays.sort(fieldArray,new RangeComparator());
        
        int shotPointer=0,fieldPointer=0;
        
        while(fieldPointer<m && shotPointer <n){
            if(fieldArray[fieldPointer].high<shotArray[shotPointer].low)
                fieldPointer++;
            
            else if(fieldArray[fieldPointer].low>shotArray[shotPointer].high)
                shotPointer++;
            
            else{
                    int countPointer=shotPointer;
                
                    while(countPointer<n && fieldArray[fieldPointer].high>=shotArray[countPointer].low){
                        
                            if(Range.isOverlapping(fieldArray[fieldPointer],shotArray[countPointer]))
                                    count++;
                            
                            countPointer++;
               }
                    fieldPointer++;
            }
            }  
        System.out.println(count);
        }
        
    }  

Problem solution in C++ programming.

#include <bits/stdc++.h>
using namespace std;
#define fo(i,n) for(int i=0;i<(n);i++)
#define MOD 1000000007
#define PB push_back
typedef long long ll;

int N, M;
vector<int> p, m;
ll ans;

int main () {
        scanf("%d %d", &N, &M);
        fo(i, N) {
                int a, b; scanf("%d %d", &a, &b);
                p.PB(a), m.PB(b+1);
        }
        sort(p.begin(), p.end()), sort(m.begin(), m.end());
        fo(i, M) {
                int a, b; scanf("%d %d", &a, &b);
                ans += N
                        - int(upper_bound(m.begin(), m.end(), a) - m.begin())
                        - int(p.end() - upper_bound(p.begin(), p.end(), b));
        }
        printf("%lldn", ans);
        return 0;
}

Problem solution in C programming.

#include <stdio.h>
#include <stdlib.h>
void sort_a(int*a,int size);
void merge(int*a,int*left,int*right,int left_size, int right_size);
int get_i(int*a,int num,int size);
int med(int*a,int size);
int h[100000],t[100000];

int main(){
  int N,M,x,y,tt,i;
  long long ans=0;
  scanf("%d%d",&N,&M);
  for(i=0;i<N;i++)
    scanf("%d%d",h+i,t+i);
  sort_a(h,N);
  sort_a(t,N);
  for(i=0;i<M;i++){
    scanf("%d%d",&x,&y);
    tt=0;
    tt+=get_i(t,x,N);
    tt+=N-get_i(h,y+1,N);
    tt=N-tt;
    ans+=tt;
  }
  printf("%lld",ans);
  return 0;
}
void sort_a(int*a,int size){
  if (size < 2)
    return;
  int m = (size+1)/2,i;
  int *left,*right;
  left=(int*)malloc(m*sizeof(int));
  right=(int*)malloc((size-m)*sizeof(int));
  for(i=0;i<m;i++)
    left[i]=a[i];
  for(i=0;i<size-m;i++)
    right[i]=a[i+m];
  sort_a(left,m);
  sort_a(right,size-m);
  merge(a,left,right,m,size-m);
  free(left);
  free(right);
  return;
}
void merge(int*a,int*left,int*right,int left_size, int right_size){
    int i = 0, j = 0;
    while (i < left_size|| j < right_size) {
        if (i == left_size) {
            a[i+j] = right[j];
            j++;
        } else if (j == right_size) {
            a[i+j] = left[i];
            i++;
        } else if (left[i] <= right[j]) {
            a[i+j] = left[i];
            i++;                
        } else {
            a[i+j] = right[j];
            j++;
        }
    }
    return;
}
int get_i(int*a,int num,int size){
  if(size==0)
    return 0;
  if(num>med(a,size))
    return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
  else
    return get_i(a,num,(size-1)>>1);
}
int med(int*a,int size){
  return a[(size-1)>>1];
}

Problem solution in JavaScript programming.

import java.io.*;
import java.util.*;
public class Solution {
public static class FenwikTree {
    private int BIT[];

    public FenwikTree(int size) {
        BIT = new int[size];
    }

    public void add(int index, int value) {
        while (index <= BIT.length) {
            BIT[index-1] += value;
            index += (index & -index);
        }
    }

    public int sum(int index) {
        int s = 0;

        while (index > 0) {
            s += BIT[index-1];
            index -= (index & -index);
        }

        return s;
    }
}


public static void main(String[] args) {
    Scanner sc = new Scanner (System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();

        FenwikTree aTree = new FenwikTree(100000);
        FenwikTree bTree = new FenwikTree(100000);

        for (int i = 0;i < n; i++) {
            aTree.add(sc.nextInt(), 1);
            bTree.add(sc.nextInt(), 1);
        }

        int sum = 0;
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt();   
            int b = sc.nextInt();
            sum += m - bTree.sum(a-1) - (m - aTree.sum(b));
        }
        System.out.println(sum);
}
}