Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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];
}
#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;
}
#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);
}
}
#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)
#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();
});
function readLine() {
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();
}