Dada una array arr[] que contiene N intervalos, la tarea es verificar si los intervalos se pueden sumar o restar por X después de lo cual no hay intervalos superpuestos. Sea X cualquier número real.
Ejemplos:
Entrada: arr[] = {[1, 3], [2, 4], [4, 5], [5, 6]}
Salida: SI
Explicación:
Podemos sumar X = 1000e
intervalos
y restar X = 1000 ene
intervalos.
Entrada: arr[] = {[1, 2], [3, 4], [5, 6]}
Salida: SÍ
Explicación:
No hay intervalos superpuestos.Entrada: arr[] = {[1, 4], [2, 2], [2, 3]}
Salida: NO
Explicación:
No hay X posible tal que los intervalos no se superpongan.
Enfoque: la idea es comparar cada intervalo como un par con la ayuda de los bucles anidados y luego, para cada intervalo, verificar que se superpongan. Si tres intervalos se superponen entre sí, no hay forma de sumar ningún valor de X para formar No superpuestos.
Podemos encontrar si hay una superposición en los tres intervalos entre sí usando estructuras de datos de búsqueda de unión o conjunto disjunto .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to check if the
// intervals can be non-overlapping
// by adding or subtracting X to
// each interval
#include <bits/stdc++.h>
using namespace std;
// Function to check if two intervals
// overlap with each other
bool checkOverlapping(vector<int> a,
vector<int> b)
{
if (a[0] < b[0])
{
a.swap(b);
}
// Condition to check if the
// intervals overlap
if (b[0]<= a[0]<= b[1])
return true;
return false;
}
// Function to check if there
// is a existing overlapping
// intervals
int find(int a[], int i)
{
if (a[i] == i)
return i;
// Path compression
a[i] = find(a, a[i]);
return a[i];
}
// Union of two intervals
// Returns True
// if there is a overlapping
// with the same another interval
bool Union(int a[], int x, int y)
{
int xs = find(a, x);
int ys = find(a, y);
if (xs == ys)
{
// Both have same
// another
// overlapping interval
return true;
}
a[ys]= xs;
return false;
}
// Function to check if the intervals
// can be added by X to form
// non-overlapping intervals
bool checkNonOverlapping(vector<vector<int>> arr,
int n)
{
int dsu[n + 1];
for(int i = 0; i < n + 1; i++)
dsu[i] = i;
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If the intervals
// overlaps
// we will union them
if (checkOverlapping(arr[i], arr[j]))
{
if (Union(dsu, i, j))
{
return false;
}
}
}
}
// There is no cycle
return true;
}
// Driver Code
int main()
{
vector<vector<int>> arr ={ { 1, 4 },
{ 2, 2 },
{ 2, 3 } };
int n = arr.size();
if (checkNonOverlapping(arr,n))
{
cout << "YES" << endl;
}
else
{
cout << "NO" << endl;
}
return 0;
}
// This code is contributed by divyeshrabadiya07
Java
// Java implementation to check if the
// intervals can be non-overlapping by
// by adding or subtracting
// X to each interval
import java.io.*;
import java.util.*;
class GFG{
// Function to check if two intervals
// overlap with each other
public static Boolean checkOverlapping(
ArrayList<Integer> a, ArrayList<Integer> b)
{
if (a.get(0) < b.get(0))
{
int temp = a.get(0);
a.set(0, b.get(0));
b.set(0, temp);
temp = a.get(1);
a.set(1, b.get(1));
b.set(1, temp);
}
// Condition to check if the
// intervals overlap
if (b.get(0) <= a.get(0) &&
a.get(0) <= b.get(1))
return true;
return false;
}
// Function to check if there
// is a existing overlapping
// intervals
public static int find(ArrayList<Integer> a, int i)
{
if (a.get(i) == i)
{
return i;
}
// Path compression
a.set(i,find(a, a.get(i)));
return a.get(i);
}
// Union of two intervals Returns True.
// If there is a overlapping
// with the same another interval
public static Boolean union(ArrayList<Integer> a,
int x, int y)
{
int xs = find(a, x);
int ys = find(a, y);
if (xs == ys)
{
// Both have same
// another overlapping
// interval
return true;
}
a.set(ys, xs);
return false;
}
// Function to check if the intervals
// can be added by X to form
// non-overlapping intervals
public static Boolean checkNonOverlapping(
ArrayList<ArrayList<Integer>> arr, int n)
{
ArrayList<Integer> dsu = new ArrayList<Integer>();
for(int i = 0; i < n + 1; i++)
{
dsu.add(i);
}
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If the intervals
// overlaps we will
// union them
if (checkOverlapping(arr.get(i),
arr.get(j)))
{
if (union(dsu, i, j))
{
return false;
}
}
}
}
// There is no cycle
return true;
}
// Driver Code
public static void main(String[] args)
{
ArrayList<
ArrayList<Integer>> arr = new ArrayList<
ArrayList<Integer>>();
arr.add(new ArrayList<Integer>(Arrays.asList(1, 4)));
arr.add(new ArrayList<Integer>(Arrays.asList(2, 2)));
arr.add(new ArrayList<Integer>(Arrays.asList(2, 3)));
int n = arr.size();
if (checkNonOverlapping(arr,n))
{
System.out.println("YES");
}
else
{
System.out.println("NO");
}
}
}
// This code is contributed by avanitrachhadiya2155
Python3
# Python3 implementation to check if
# the intervals can be non-overlapping by
# by adding or subtracting
# X to each interval
# Function to check if two intervals
# overlap with each other
def checkOverlapping(a, b):
a, b = max(a, b), min(a, b)
# Condition to check if the
# intervals overlap
if b[0]<= a[0]<= b[1]:
return True
return False
# Function to check if there
# is a existing overlapping
# intervals
def find(a, i):
if a[i]== i:
return i
# Path compression
a[i]= find(a, a[i])
return a[i]
# Union of two intervals
# Returns True
# if there is a overlapping
# with the same another interval
def union(a, x, y):
xs = find(a, x)
ys = find(a, y)
if xs == ys:
# Both have same
# another
# overlapping interval
return True
a[ys]= xs
return False
# Function to check if the intervals
# can be added by X to form
# non-overlapping intervals
def checkNonOverlapping(arr, n):
dsu =[i for i in range(n + 1)]
for i in range(n):
for j in range(i + 1, n):
# If the intervals
# overlaps
# we will union them
if checkOverlapping(arr[i], \
arr[j]):
if union(dsu, i, j):
return False
# There is no cycle
return True
# Driver Code
if __name__ == "__main__":
arr =[[1, 4], [2, 2], [2, 3]]
n = len(arr)
print("YES" if checkNonOverlapping\
(arr, n) else "NO")
C#
// C# implementation to check if
// the intervals can be non-overlapping by
// by adding or subtracting
// X to each interval
using System;
using System.Collections.Generic;
class GFG {
// Function to check if two intervals
// overlap with each other
static bool checkOverlapping(List<int> a, List<int> b)
{
if(a[0] < b[0])
{
int temp = a[0];
a[0] = b[0];
b[0] = temp;
temp = a[1];
a[1] = b[1];
b[1] = temp;
}
// Condition to check if the
// intervals overlap
if(b[0] <= a[0] && a[0] <= b[1])
return true;
return false;
}
// Function to check if there
// is a existing overlapping
// intervals
static int find(List<int> a, int i)
{
if(a[i] == i)
{
return i;
}
// Path compression
a[i] = find(a, a[i]);
return a[i];
}
// Union of two intervals
// Returns True
// if there is a overlapping
// with the same another interval
static bool union(List<int> a, int x, int y)
{
int xs = find(a, x);
int ys = find(a, y);
if(xs == ys)
{
// Both have same
// another
// overlapping interval
return true;
}
a[ys] = xs;
return false;
}
// Function to check if the intervals
// can be added by X to form
// non-overlapping intervals
static bool checkNonOverlapping(List<List<int>> arr, int n)
{
List<int> dsu = new List<int>();
for(int i = 0; i < n + 1; i++)
{
dsu.Add(i);
}
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// If the intervals
// overlaps
// we will union them
if(checkOverlapping(arr[i], arr[j]))
{
if(union(dsu, i, j))
{
return false;
}
}
}
}
// There is no cycle
return true;
}
static void Main() {
List<List<int>> arr = new List<List<int>>();
arr.Add(new List<int> { 1, 4 });
arr.Add(new List<int> { 2, 2 });
arr.Add(new List<int> { 2, 3 });
int n = arr.Count;
if (checkNonOverlapping(arr,n))
{
Console.WriteLine("YES");
}
else
{
Console.WriteLine("NO");
}
}
}
// This code is contributed by divyes072019
Javascript
<script>
// JavaScript implementation to check if
// the intervals can be non-overlapping by
// by adding or subtracting
// X to each interval
// Function to check if two intervals
// overlap with each other
function checkOverlapping(a, b)
{
if(a[0] < b[0])
{
var temp = a[0];
a[0] = b[0];
b[0] = temp;
temp = a[1];
a[1] = b[1];
b[1] = temp;
}
// Condition to check if the
// intervals overlap
if(b[0] <= a[0] && a[0] <= b[1])
return true;
return false;
}
// Function to check if there
// is a existing overlapping
// intervals
function find(a, i)
{
if(a[i] == i)
{
return i;
}
// Path compression
a[i] = find(a, a[i]);
return a[i];
}
// Union of two intervals
// Returns True
// if there is a overlapping
// with the same another interval
function union(a, x, y)
{
var xs = find(a, x);
var ys = find(a, y);
if(xs == ys)
{
// Both have same
// another
// overlapping interval
return true;
}
a[ys] = xs;
return false;
}
// Function to check if the intervals
// can be added by X to form
// non-overlapping intervals
function checkNonOverlapping(arr, n)
{
var dsu = [];
for(var i = 0; i < n + 1; i++)
{
dsu.push(i);
}
for(var i = 0; i < n; i++)
{
for(var j = i + 1; j < n; j++)
{
// If the intervals
// overlaps
// we will union them
if(checkOverlapping(arr[i], arr[j]))
{
if(union(dsu, i, j))
{
return false;
}
}
}
}
// There is no cycle
return true;
}
var arr = Array();
arr.push([1, 4 ]);
arr.push([2, 2 ]);
arr.push([2, 3 ]);
var n = arr.length;
if (checkNonOverlapping(arr,n))
{
document.write("YES");
}
else
{
document.write("NO");
}
</script>
Producción:
NO
Complejidad de tiempo: O(n*n*log(n))
Espacio auxiliar: O(n), ya que se utiliza espacio extra
Publicación traducida automáticamente
Artículo escrito por pedastrian y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA