## Algorithm

Problem Name: Data Structures - Mr. X and His Shots

In this HackerRank in Data Structures - Mr. X and His Shots solutions

A cricket match is going to be held. The field is represented by a 1D plane. A cricketer, Mr. X has N favorite shots. Each shot has a particular range. The range of the i**th shot is from Ai  to Bi. That means his favorite shot can be anywhere in this range. Each player on the opposite team can field only in a particular range. Player i can field from Ci to D. You are given the N favorite shots of Mr. X and the range of M players.

Si represents the strength of each player i.e. the number of shots player i can stop.

Game Rules: A player can stop the i**th shot if the range overlaps with the player's fielding range.

For more clarity about overlapping, study the following figure:

Constraints:

1 <= N, M <= 10**5

1 <= Ai, Bi, Ci, Di <= 10**5

Sample Input

4 4
1 2
2 3
4 5
6 7
1 5
2 3
4 7
5 7


Sample Output

9


Explanation

Player 1 can stop the 1st, 2nd and 3rd shot so the strength is 3.

Player 2 can stop the 1st and 2nd shot so the strength is 2.

Player 3 can stop the 3rd and 4th shot so the strength is 2.

Player 4 can stop the 3rd and 4th shot so the strength is 2.

The sum of the strengths of all the players is 3 + 2 + 2 + 2 = 9

## Code Examples

### #1 Code Example with C Programming

Code - 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];
}

Copy The Code &

### #2 Code Example with C++ Programming

Code - 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;
}

Copy The Code &

### #3 Code Example with Java Programming

Code - 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
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);
}

}

Copy The Code &

### #4 Code Example with Python Programming

Code - 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)

Copy The Code &

### #5 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
inputString += inputStdin;
});

process.stdin.on('end', function() {
inputString = inputString.split('\n');

main();
});

return inputString[currentLine++];
}

/*
* Complete the 'solve' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
*  1. 2D_INTEGER_ARRAY shots
*  2. 2D_INTEGER_ARRAY players
*/

function lowerBound(arr, cmp) {
let l = 0;
let r = arr.length;
while (l  <  r) {
const m = (l + r) >> 1;
if (cmp(arr[m])  <  0) {
l = m + 1;
} else {
r = m;
}
}
return l;
}

function solve(shots, players) {
const aa = shots.map(e => e[0]).sort((x, y) => x - y);
const bb = shots.map(e => e[1]).sort((x, y) => x - y);
let sum = 0;
for (const [c, d] of players) {
// 1st lowerBound is number of players whose a  < = d
// 2nd lowerBound is number of players whose b < c
sum += lowerBound(aa, (a) => a - (d + 1)) -
lowerBound(bb, (b) => b - c);
}
return sum;
}

function main() {
const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' '); const n = parseInt(firstMultipleInput[0], 10); const m = parseInt(firstMultipleInput[1], 10); let shots = Array(n); for (let i = 0; i < n; i++) { shots[i] = readLine().replace(/\s+$/g, '').split(' ').map(shotsTemp => parseInt(shotsTemp, 10));
}

let players = Array(m);

for (let i = 0; i  <  m; i++) {
players[i] = readLine().replace(/\s+\$/g, '').split(' ').map(playersTemp => parseInt(playersTemp, 10));
}

const result = solve(shots, players);

ws.write(result + '\n');

ws.end();
}

Copy The Code &