Dados N intervalos de la forma [l, r] , la tarea es encontrar la intersección de todos los intervalos. Una intersección es un intervalo que se encuentra dentro de todos los intervalos dados. Si no existe tal intersección, imprima -1 .
Ejemplos:
Entrada: arr[] = {{1, 6}, {2, 8}, {3, 10}, {5, 8}}
Salida: [5, 6]
[5, 6] es el intervalo común que se encuentra en todos los intervalos dados.
Entrada: arr[] = {{1, 6}, {8, 18}}
Salida: -1
No existe intersección entre los dos rangos dados.
Acercarse:
- Comience considerando el primer intervalo como la respuesta requerida.
- Ahora, a partir del segundo intervalo, intente buscar la intersección. Pueden darse dos casos:
- No existe intersección entre [l1, r1] y [l2, r2] . Posible solo cuando r1 < l2 o r2 < l1 . En tal caso, la respuesta será 0 , es decir, no existe ninguna intersección.
- Existe una intersección entre [l1, r1] y [l2, r2] . Entonces la intersección requerida será [max(l1, l2), min(r1, r2)] .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Function to print the intersection
void findIntersection(int intervals[][2], int N)
{
// First interval
int l = intervals[0][0];
int r = intervals[0][1];
// Check rest of the intervals and find the intersection
for (int i = 1; i < N; i++) {
// If no intersection exists
if (intervals[i][0] > r || intervals[i][1] < l) {
cout << -1;
return;
}
// Else update the intersection
else {
l = max(l, intervals[i][0]);
r = min(r, intervals[i][1]);
}
}
cout << "[" << l << ", " << r << "]";
}
// Driver code
int main()
{
int intervals[][2] = {
{ 1, 6 },
{ 2, 8 },
{ 3, 10 },
{ 5, 8 }
};
int N = sizeof(intervals) / sizeof(intervals[0]);
findIntersection(intervals, N);
}
Java
// Java implementation of the approach
import java.io.*;
class GFG
{
// Function to print the intersection
static void findIntersection(int intervals[][], int N)
{
// First interval
int l = intervals[0][0];
int r = intervals[0][1];
// Check rest of the intervals
// and find the intersection
for (int i = 1; i < N; i++)
{
// If no intersection exists
if (intervals[i][0] > r ||
intervals[i][1] < l)
{
System.out.println(-1);
return;
}
// Else update the intersection
else
{
l = Math.max(l, intervals[i][0]);
r = Math.min(r, intervals[i][1]);
}
}
System.out.println ("[" + l +", " + r + "]");
}
// Driver code
public static void main (String[] args)
{
int intervals[][] = {{ 1, 6 },
{ 2, 8 },
{ 3, 10 },
{ 5, 8 }};
int N = intervals.length;
findIntersection(intervals, N);
}
}
// This Code is contributed by ajit..
Python
# Python3 implementation of the approach
# Function to print the intersection
def findIntersection(intervals,N):
# First interval
l = intervals[0][0]
r = intervals[0][1]
# Check rest of the intervals
# and find the intersection
for i in range(1,N):
# If no intersection exists
if (intervals[i][0] > r or intervals[i][1] < l):
print(-1)
# Else update the intersection
else:
l = max(l, intervals[i][0])
r = min(r, intervals[i][1])
print("[",l,", ",r,"]")
# Driver code
intervals= [
[ 1, 6 ],
[ 2, 8 ],
[ 3, 10 ],
[ 5, 8 ]
]
N =len(intervals)
findIntersection(intervals, N)
# this code is contributed by mohit kumar
C#
// C# implementation of the approach
using System;
class GFG
{
// Function to print the intersection
static void findIntersection(int [,]intervals, int N)
{
// First interval
int l = intervals[0, 0];
int r = intervals[0, 1];
// Check rest of the intervals
// and find the intersection
for (int i = 1; i < N; i++)
{
// If no intersection exists
if (intervals[i, 0] > r ||
intervals[i, 1] < l)
{
Console.WriteLine(-1);
return;
}
// Else update the intersection
else
{
l = Math.Max(l, intervals[i, 0]);
r = Math.Min(r, intervals[i, 1]);
}
}
Console.WriteLine("[" + l + ", " + r + "]");
}
// Driver code
public static void Main()
{
int [,]intervals = {{ 1, 6 }, { 2, 8 },
{ 3, 10 }, { 5, 8 }};
int N = intervals.GetLength(0);
findIntersection(intervals, N);
}
}
// This code is contributed by Ryuga
PHP
<?php
// PHP implementation of the approach
// Function to print the intersection
function findIntersection($intervals, $N)
{
// First interval
$l = $intervals[0][0];
$r = $intervals[0][1];
// Check rest of the intervals and
// find the intersection
for ($i = 1; $i < $N; $i++)
{
// If no intersection exists
if ($intervals[$i][0] > $r ||
$intervals[$i][1] < $l)
{
echo -1;
return;
}
// Else update the intersection
else
{
$l = max($l, $intervals[$i][0]);
$r = min($r, $intervals[$i][1]);
}
}
echo "[" . $l . ", " . $r . "]";
}
// Driver code
$intervals = array(array(1, 6), array(2, 8),
array(3, 10), array(5, 8));
$N = sizeof($intervals);
findIntersection($intervals, $N);
// This code is contributed
// by Akanksha Rai
?>
Javascript
<script>
// Javascript implementation of the approach
// Function to print the intersection
function findIntersection(intervals, N)
{
// First interval
let l = intervals[0][0];
let r = intervals[0][1];
// Check rest of the intervals
// and find the intersection
for (let i = 1; i < N; i++)
{
// If no intersection exists
if (intervals[i][0] > r ||
intervals[i][1] < l)
{
document.write(-1 + "</br>");
return;
}
// Else update the intersection
else
{
l = Math.max(l, intervals[i][0]);
r = Math.min(r, intervals[i][1]);
}
}
document.write("[" + l +", " + r + "]" + "</br>");
}
let intervals = [[ 1, 6 ],
[ 2, 8 ],
[ 3, 10],
[ 5, 8 ]];
let N = intervals.length;
findIntersection(intervals, N);
</script>
Producción:
[5, 6]