Given an array arr[] containing N intervals, the task is to check that if the intervals can be added or subtracted by X after which there are no overlapping intervals. Here X be any real number.
Examples:
Input: arr[] = {[1, 3], [2, 4], [4, 5], [5, 6]}
Output: YES
Explanation:
We can add X = 1000 inand
intervals
ans subtract X = 1000 inand
intervals.
Input: arr[] = {[1, 2], [3, 4], [5, 6]}
Output: YES
Explanation:
No intervals are overlapping.Input: arr[] = {[1, 4], [2, 2], [2, 3]}
Output: NO
Explanation:
There is no possible X such that intervals don’t overlap.
and 
intervals 
and 
intervals.Approach: The idea is to compare each intervals as a pair with the help of the Nested loops and then for each interval check that they overlap. If any three intervals overlap with each other then there is no way to add any value of X to form Non-overlapping.
We can find if there is an overlapping in the three intervals with each other using union find or disjoint set data structures.
Below is the implementation of the above approach:
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 intervalimport java.io.*;import java.util.*;class GFG{ // Function to check if two intervals // overlap with each otherpublic 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 // intervalspublic 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 intervalpublic 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 intervalspublic 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 Codepublic 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 otherdef 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 # intervalsdef 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 intervaldef 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 intervalsdef 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 Codeif __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 intervalusing 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 otherfunction 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 // intervalsfunction 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 intervalfunction 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 intervalsfunction 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> |
Output:
NO
Time Complexity: O(n*n*log(n))
Auxiliary Space: O(n),as extra space is used
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
