Dados N rangos y Q consultas que consisten en números. Cada rango consta de L y R. La tarea es verificar si el número dado se encuentra en alguno de los rangos dados o no para cada consulta.
Nota: No hay rango superpuesto.
Ejemplos:
Entrada: range[] = { {5, 6}, {1, 3}, {8, 10}
Q = 4
1.ª consulta: 2
2.ª consulta: 3
3.ª consulta: 4
4.ª consulta: 7
Salida:
Sí
Sí
No
No
1.ª consulta: 2 se encuentra en un rango 1-3
2da consulta: 3 se encuentra en un rango 1-3
3ra consulta: 4 no se encuentra en ninguno de los rangos dados.
Cuarta consulta: 7 no se encuentra en ninguno de los rangos dados.
Enfoque: a continuación se muestra el algoritmo paso a paso para resolver este problema:
- Hash la L de cada rango como 1, y hash la R de cada rango como 2.
- Empuje la L y la R por separado en un recipiente.
- Ordene los elementos en el contenedor, todo el rango L y R estarán adyacentes entre sí para que no se superpongan.
- Para cada consulta, use la búsqueda binaria para encontrar la primera aparición de un número igual o mayor que él. Esto se puede hacer usando la función lower_bound .
- Si hay algún valor que es igual a la consulta, entonces el número se superpone al rango.
- Si no hay ningún valor que sea igual a la consulta, verifique si el elemento mayor tiene un hash de 1 o 2.
- Si se codifica como 1, entonces el número no se superpone, de lo contrario, se superpone.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if the
// number lies in given range
#include <bits/stdc++.h>
using namespace std;
// Function that answers every query
void answerQueries(int a[][2], int n, int queries[], int q)
{
// container to store all range
vector<int> v;
// hash the L and R
unordered_map<int, int> mpp;
// Push the element to container
// and hash the L and R
for (int i = 0; i < n; i++) {
v.push_back(a[i][0]);
mpp[a[i][0]] = 1;
v.push_back(a[i][1]);
mpp[a[i][1]] = 2;
}
// sort the elements in container
sort(v.begin(), v.end());
for (int i = 0; i < q; i++) {
// each query
int num = queries[i];
// get the number same or greater than integer
int ind = lower_bound(v.begin(), v.end(), num) - v.begin();
// if it lies
if (v[ind] == num) {
cout << "Yes\n";
}
else {
// check if greater is hashed as 2
if (mpp[v[ind]] == 2)
cout << "Yes\n";
else // check if greater is hashed as 1
cout << "No\n";
}
}
}
// Driver code
int main()
{
int a[][2] = { { 5, 6 }, { 1, 3 }, { 8, 10 } };
int n = 3;
int queries[] = { 2, 3, 4, 7 };
int q = sizeof(queries) / sizeof(queries[0]);
// function call to answer queries
answerQueries(a, n, queries, q);
return 0;
}
Java
// Java program to check if the
// number lies in given range
import java.io.*;
import java.util.*;
class GFG
{
// Function that answers every query
static void answerQueries(int[][] a, int n,
int[] queries, int q)
{
// container to store all range
Vector<Integer> v = new Vector<>();
// hash the L and R
HashMap<Integer, Integer> mpp = new HashMap<>();
// Push the element to container
// and hash the L and R
for (int i = 0; i < n; i++)
{
v.add(a[i][0]);
mpp.put(a[i][0], 1);
v.add(a[i][1]);
mpp.put(a[i][1], 2);
}
// sort the elements in container
Collections.sort(v);
for (int i = 0; i < q; i++)
{
// each query
int num = queries[i];
// get the number same or greater than integer
int ind = lowerBound(v, num);
// if it lies
if (ind >= 0 && v.elementAt(ind) == num)
System.out.println("Yes");
else
{
// check if greater is hashed as 2
if (ind >= 0 && mpp.get(v.elementAt(ind)) == 2)
System.out.println("Yes");
else // check if greater is hashed as 1
System.out.println("No");
}
}
}
// Lower bound implementation
static int lowerBound(Vector<Integer> array, int value)
{
int low = 0;
int high = array.size();
while (low < high)
{
final int mid = (low + high) / 2;
if (value <= array.elementAt(mid))
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Driver Code
public static void main(String[] args)
{
int[][] a = {{ 5, 6 }, { 1, 3 }, { 8, 10 }};
int n = 3;
int[] queries = {2, 3, 4, 7};
int q = queries.length;
// function call to answer queries
answerQueries(a, n, queries, q);
}
}
// This code is contributed by
// sanjeev2552
Python3
# Python program to check if the
# number lies in given range
from bisect import bisect_left as lower_bound
# Function that answers every query
def answerQueries(a: list, n, queries: list, q):
# container to store all range
v = list()
# hash the L and R
mpp = dict()
# Push the element to container
# and hash the L and R
for i in range(n):
v.append(a[i][0])
mpp[a[i][0]] = 1
v.append(a[i][1])
mpp[a[i][1]] = 2
# sort the elements in container
v.sort()
for i in range(q):
# each query
num = queries[i]
# get the number same or greater than integer
ind = lower_bound(v, num)
# if it lies
if v[ind] == num:
print("Yes")
else:
# check if greater is hashed as 2
if mpp[v[ind]] == 2:
print("Yes")
# check if greater is hashed as 1
else:
print("No")
# Driver Code
if __name__ == "__main__":
a = [[5, 6], [1, 3], [8, 10]]
n = 3
queries = [2, 3, 4, 7]
q = len(queries)
# function call to answer queries
answerQueries(a, n, queries, q)
# This code is contributed by
# sanjeev2552
C#
// C# program to check if the
// number lies in given range
using System;
using System.Collections.Generic;
class GFG
{
// Function that answers every query
static void answerQueries(int[,] a, int n,
int[] queries, int q)
{
// container to store all range
List<int> v = new List<int>();
// hash the L and R
Dictionary<int, int> mpp = new Dictionary<int, int>();
// Push the element to container
// and hash the L and R
for (int i = 0; i < n; i++)
{
v.Add(a[i, 0]);
if(!mpp.ContainsKey(a[i, 0]))
mpp.Add(a[i, 0], 1);
v.Add(a[i, 1]);
if(!mpp.ContainsKey(a[i, 1]))
mpp.Add(a[i, 1], 2);
}
// sort the elements in container
v.Sort();
for (int i = 0; i < q; i++)
{
// each query
int num = queries[i];
// get the number same or greater than integer
int ind = lowerBound(v, num);
// if it lies
if (ind >= 0 && v[ind] == num)
Console.WriteLine("Yes");
else
{
// check if greater is hashed as 2
if (ind >= 0 && mpp[v[ind]] == 2)
Console.WriteLine("Yes");
else // check if greater is hashed as 1
Console.WriteLine("No");
}
}
}
// Lower bound implementation
static int lowerBound(List<int> array, int value)
{
int low = 0;
int high = array.Count;
while (low < high)
{
int mid = (low + high) / 2;
if (value <= array[mid])
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Driver Code
public static void Main(String[] args)
{
int[,] a = {{ 5, 6 }, { 1, 3 }, { 8, 10 }};
int n = 3;
int[] queries = {2, 3, 4, 7};
int q = queries.Length;
// function call to answer queries
answerQueries(a, n, queries, q);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program to check if the
// number lies in given range
// Function that answers every query
function answerQueries(a, n, queries, q)
{
// container to store all range
let v = [];
// hash the L and R
let mpp = new Map();
// Push the element to container
// and hash the L and R
for (let i = 0; i < n; i++)
{
v.push(a[i][0]);
mpp.set(a[i][0], 1);
v.push(a[i][1]);
mpp.set(a[i][1], 2);
}
// sort the elements in container
v.sort(function(a,b){return a-b;});
for (let i = 0; i < q; i++)
{
// each query
let num = queries[i];
// get the number same or greater than integer
let ind = lowerBound(v, num);
// if it lies
if (ind >= 0 && v[ind] == num)
document.write("Yes<br>");
else
{
// check if greater is hashed as 2
if (ind >= 0 && mpp.get(v[ind]) == 2)
document.write("Yes<br>");
else // check if greater is hashed as 1
document.write("No<br>");
}
}
}
// Lower bound implementation
function lowerBound(array,value)
{
let low = 0;
let high = array.length;
while (low < high)
{
let mid = Math.floor((low + high) / 2);
if (value <= array[mid])
{
high = mid;
}
else
{
low = mid + 1;
}
}
return low;
}
// Driver Code
let a=[[ 5, 6 ], [ 1, 3 ], [ 8, 10 ]];
let n = 3;
let queries=[2, 3, 4, 7];
let q = queries.length;
// function call to answer queries
answerQueries(a, n, queries, q);
// This code is contributed by rag2127
</script>
Producción:
Yes Yes No No
Complejidad de tiempo: O(n*log(n)+q*log(n))
Espacio auxiliar: O(n)