Algorithm


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

Problem Link: https://www.hackerrank.com/challenges/x-and-his-shots/problem?isFullScreen=true

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 & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor

#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 & Try With Live Editor

#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();
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Kindergarten Adventures solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Find Maximum Index Product solution in Hackerrank - Hacerrank solution C, C++, java,js, Python