## 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,t;

int main(){
int N,M,x,y,tt,i;
long long ans=0;
scanf("%d%d",&N,&M);
for(i=0;imed(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 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.high)
return false;
else
return true;
}
}
class RangeComparator implements Comparator{

@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;ishotArray[shotPointer].high)
shotPointer++;

else{
int countPointer=shotPointer;

while(countPointer=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:
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).sort((x, y) => x - y);
const bb = shots.map(e => e).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, 10); const m = parseInt(firstMultipleInput, 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 &