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;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 & 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 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.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 & 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

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