Dada una array arr[] que consta de N intervalos de la forma [L, R] , donde L, R denota las posiciones inicial y final del intervalo, la tarea es contar el número máximo de intervalos con los que un intervalo puede intersecarse El uno al otro.
Ejemplos:
Entrada: arr[] = {{1, 2}, {3, 4}, {2, 5}}
Salida: 3
Explicación: El conjunto de intervalos necesarios son {1, 2}, {2, 5}, {3 , 4} como {2, 5} intersecan todos los demás intervalos.Entrada: arr[] = {{1, 3}, {2, 4}, {3, 5}, {8, 11}}
Salida: 3
Explicación: El conjunto de intervalos necesarios son {1, 3}, {2 , 4}, {3, 5} como {2, 4} intersecan todos los demás intervalos.
Enfoque ingenuo: el enfoque más simple es atravesar la array y, para cada intervalo, contar la cantidad de intervalos que intersecta usando un bucle anidado . Después de verificar cada intervalo, imprima el número máximo de intervalos que un intervalo puede intersectar.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to count the maximum number
// of intervals that an interval
// can intersect
void findMaxIntervals(
vector<pair<int, int> > v, int n)
{
// Store the required answer
int maxi = 0;
// Traverse all the intervals
for (int i = 0; i < n; i++) {
// Store the number of
// intersecting intervals
int c = n;
// Iterate in the range[0, n-1]
for (int j = 0; j < n; j++) {
// Check if jth interval lies
// outside the ith interval
if (v[i].second < v[j].first
|| v[i].first > v[j].second) {
c--;
}
}
// Update the overall maximum
maxi = max(c, maxi);
}
// Print the answer
cout << maxi;
}
// Driver Code
int main()
{
vector<pair<int, int> > arr
= { { 1, 2 },
{ 3, 4 },
{ 2, 5 } };
int N = arr.size();
// Function Call
findMaxIntervals(arr, N);
return 0;
}
Java
// Java implementation of the approach
import java.util.*;
class GFG
{
static class Pair
{
int first, second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
}
// Function to count the maximum number
// of intervals that an interval
// can intersect
static void findMaxIntervals(ArrayList<Pair> v, int n)
{
// Store the required answer
int maxi = 0;
// Traverse all the intervals
for (int i = 0; i < n; i++)
{
// Store the number of
// intersecting intervals
int c = n;
// Iterate in the range[0, n-1]
for (int j = 0; j < n; j++) {
// Check if jth interval lies
// outside the ith interval
if (v.get(i).second < v.get(j).first
|| v.get(i).first > v.get(j).second) {
c--;
}
}
// Update the overall maximum
maxi = Math.max(c, maxi);
}
// Print the answer
System.out.print(maxi);
}
// Driver code
public static void main(String[] args)
{
ArrayList<Pair> arr = new ArrayList<>();
arr.add(new Pair(1,2));
arr.add(new Pair(3,4));
arr.add(new Pair(2,5));
int N = arr.size();
// Function Call
findMaxIntervals(arr, N);
}
}
// This code is contributed by susmitakundugoaldnga.
Python3
# Python3 program for the above approach # Function to count the maximum number # of intervals that an interval # can intersect def findMaxIntervals(v, n) : # Store the required answer maxi = 0 # Traverse all the intervals for i in range(n) : # Store the number of # intersecting intervals c = n # Iterate in the range[0, n-1] for j in range(n) : # Check if jth interval lies # outside the ith interval if (v[i][1] < v[j][0] or v[i][0] > v[j][1]) : c -= 1 # Update the overall maximum maxi = max(c, maxi) # Print the answer print(maxi) # Driver code arr = [] arr.append((1,2)) arr.append((3,4)) arr.append((2,5)) N = len(arr) # Function Call findMaxIntervals(arr, N) # This code is contributed by divyeshrabadiya07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to count the maximum number
// of intervals that an interval
// can intersect
static void findMaxIntervals(List<Tuple<int, int> > v, int n)
{
// Store the required answer
int maxi = 0;
// Traverse all the intervals
for (int i = 0; i < n; i++)
{
// Store the number of
// intersecting intervals
int c = n;
// Iterate in the range[0, n-1]
for (int j = 0; j < n; j++)
{
// Check if jth interval lies
// outside the ith interval
if (v[i].Item2 < v[j].Item1
|| v[i].Item1 > v[j].Item2)
{
c--;
}
}
// Update the overall maximum
maxi = Math.Max(c, maxi);
}
// Print the answer
Console.Write(maxi);
}
// Driver code
static void Main()
{
List<Tuple<int, int>> arr = new List<Tuple<int, int>>();
arr.Add(new Tuple<int,int>(1,2));
arr.Add(new Tuple<int,int>(3,4));
arr.Add(new Tuple<int,int>(2,5));
int N = arr.Count;
// Function Call
findMaxIntervals(arr, N);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
// Function to count the maximum number
// of intervals that an interval
// can intersect
function findMaxIntervals( v, n)
{
// Store the required answer
var maxi = 0;
// Traverse all the intervals
for (var i = 0; i < n; i++) {
// Store the number of
// intersecting intervals
var c = n;
// Iterate in the range[0, n-1]
for (var j = 0; j < n; j++) {
// Check if jth interval lies
// outside the ith interval
if (v[i][1] < v[j][0]
|| v[i][0] > v[j][1]) {
c--;
}
}
// Update the overall maximum
maxi = Math.max(c, maxi);
}
// Print the answer
document.write( maxi);
}
// Driver Code
var arr
= [ [ 1, 2 ],
[ 3, 4 ],
[ 2, 5 ] ];
var N = arr.length;
// Function Call
findMaxIntervals(arr, N);
</script>
Producción:
3
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior se puede optimizar en lugar de contar el número de intersecciones, contar el número de intervalos que no se cruzan. Los intervalos que no se cruzan con un intervalo particular se pueden dividir en dos categorías inconexas: intervalos que caen completamente a la izquierda o completamente a la derecha. Usando esta idea, siga los pasos a continuación para resolver el problema:
- Cree un hashmap , digamos M , para mapear la cantidad de intervalos que no se cruzan con cada intervalo.
- Ordena los intervalos en función de su punto de partida.
- Recorre los intervalos usando la variable i
- Inicialice ans como -1 para almacenar el índice del primer intervalo que se encuentra completamente a la derecha del i -ésimo intervalo.
- Inicialice bajo y alto como (i + 1) y (N – 1) y realice una búsqueda binaria como se muestra a continuación:
- Encuentre el valor de mid como (low + high)/2 .
- Si la posición inicial de interval[mid] es mayor que la posición final de interval[i] , almacene el índice actual mid en ans y luego verifique la mitad izquierda actualizando high to (mid – 1) .
- De lo contrario, verifique en la mitad derecha actualizando bajo a (medio + 1) .
- Si el valor de ans no es -1 , agregue (N – ans) a M[interval[i]] .
- Ahora, ordene los intervalos en función de su punto final.
- Nuevamente, recorra los intervalos usando la variable i y aplique un enfoque similar al anterior para encontrar los intervalos que se encuentran completamente a la izquierda del i -ésimo intervalo.
- Después del ciclo, recorra el mapa M y almacene el valor mínimo en min .
- Imprime el valor de (N – min) como resultado.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Comparator function to sort in
// increasing order of second
// values in each pair
bool compare(pair<int, int> f,
pair<int, int> s)
{
return f.second < s.second;
}
// Function to hash a pair
struct hash_pair {
template <class T1, class T2>
size_t operator()(
const pair<T1, T2>& p) const
{
auto hash1 = hash<T1>{}(p.first);
auto hash2 = hash<T2>{}(p.second);
return hash1 ^ hash2;
}
};
// Function to count maximum number
// of intervals that an interval
// can intersect
void findMaxIntervals(
vector<pair<int, int> > v, int n)
{
// Create a hashmap
unordered_map<pair<int, int>,
int,
hash_pair>
um;
// Sort by starting position
sort(v.begin(), v.end());
// Traverse all the intervals
for (int i = 0; i < n; i++) {
// Initialize um[v[i]] as 0
um[v[i]] = 0;
// Store the starting and
// ending point of the
// ith interval
int start = v[i].first;
int end = v[i].second;
// Set low and high
int low = i + 1;
int high = n - 1;
// Store the required number
// of intervals
int ans = -1;
// Apply binary search to find
// the number of intervals
// completely lying to the
// right of the ith interval
while (low <= high) {
// Find the mid
int mid = low + (high - low) / 2;
// Condition for searching
// in the first half
if (v[mid].first > end) {
ans = mid;
high = mid - 1;
}
// Otherwise search in the
// second half
else {
low = mid + 1;
}
}
// Increment um[v[i]] by n-ans
// if ans!=-1
if (ans != -1)
um[v[i]] = n - ans;
}
// Sort by ending position
sort(v.begin(), v.end(), compare);
// Traverse all the intervals
for (int i = 0; i < n; i++) {
// Store the starting and
// ending point of the
// ith interval
int start = v[i].first;
int end = v[i].second;
// Set low and high
int low = 0;
int high = i - 1;
// Store the required number
// of intervals
int ans = -1;
// Apply binary search to
// find the number of intervals
// completely lying to the
// left of the ith interval
while (low <= high) {
int mid = low + (high - low) / 2;
if (v[mid].second < start) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
// Increment um[v[i]] by ans+1
// if ans!=-1
if (ans != -1)
um[v[i]] += (ans + 1);
}
// Store the answer
int res = 0;
// Traverse the map
for (auto it = um.begin();
it != um.end(); it++) {
// Update the overall answer
res = max(res, n - it->second);
}
// Print the answer
cout << res;
}
// Driver Code
int main()
{
vector<pair<int, int> > arr
= { { 1, 2 },
{ 3, 4 },
{ 2, 5 } };
int N = arr.size();
// Function Call
findMaxIntervals(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG
{
// Pair class to store in the um as a key
// with hashcode and equals
static class Pair
{
int first;
int second;
public Pair(int first, int second)
{
this.first = first;
this.second = second;
}
@Override public int hashCode()
{
final int prime = 31;
int result = 1;
result = prime * result + first;
result = prime * result + second;
return result;
}
@Override public boolean equals(Object obj)
{
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Pair other = (Pair)obj;
if (first != other.first)
return false;
if (second != other.second)
return false;
return true;
}
}
// Function to count maximum number
// of intervals that an interval
// can intersect
static void findMaxIntervals(ArrayList<Pair> v, int n)
{
// Create a hashmap
HashMap<Pair, Integer> um = new HashMap<>();
// Sort by starting position
Collections.sort(v, (x, y) -> x.first - y.first);
// Traverse all the intervals
for (int i = 0; i < n; i++) {
// Initialize um for v[i] as 0
um.put(v.get(i), 0);
// Store the starting and
// ending point of the
// ith interval
int start = v.get(i).first;
int end = v.get(i).second;
// Set low and high
int low = i + 1;
int high = n - 1;
// Store the required number
// of intervals
int ans = -1;
// Apply binary search to find
// the number of intervals
// completely lying to the
// right of the ith interval
while (low <= high) {
// Find the mid
int mid = low + (high - low) / 2;
// Condition for searching
// in the first half
if (v.get(mid).first > end) {
ans = mid;
high = mid - 1;
}
// Otherwise search in the
// second half
else {
low = mid + 1;
}
}
// Increment um for v[i] by n-ans
// if ans!=-1
if (ans != -1)
um.put(v.get(i), n - ans);
}
// Sort by ending position
Collections.sort(v, (x, y) -> x.second - y.second);
// Traverse all the intervals
for (int i = 0; i < n; i++) {
// Store the starting and
// ending point of the
// ith interval
int start = v.get(i).first;
int end = v.get(i).second;
// Set low and high
int low = 0;
int high = i - 1;
// Store the required number
// of intervals
int ans = -1;
// Apply binary search to
// find the number of intervals
// completely lying to the
// left of the ith interval
while (low <= high) {
int mid = low + (high - low) / 2;
if (v.get(mid).second < start) {
ans = mid;
low = mid + 1;
}
else {
high = mid - 1;
}
}
// Increment um for v[i] by ans+1
// if ans!=-1
if (ans != -1)
um.put(v.get(i),
um.get(v.get(i)) + (ans + 1));
}
// Store the answer
int res = 0;
// Traverse the map
for (int second : um.values()) {
// Update the overall answer
res = Math.max(res, n - second);
}
// Print the answer
System.out.println(res);
}
// Driver Code
public static void main(String[] args)
{
ArrayList<Pair> arr = new ArrayList<>();
arr.add(new Pair(1, 2));
arr.add(new Pair(3, 4));
arr.add(new Pair(2, 5));
int N = arr.size();
// Function Call
findMaxIntervals(arr, N);
}
}
// This code is contributed by Kingash.
Producción:
3
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por aaryaverma112 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA