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("%lld\n", 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);
}
}
0 Comments