Make given segments non-overlapping by assigning directions
Given an array arr[][] consisting of N segments of the form {L, R, V} where, [L, R] denotes a segment with velocity V in any direction, the task is to check if it is possible to assign directions as left or right to all the segments such that they do not intersect after a long period of time.
Examples:
Input: arr[][] = {{5, 7, 2}, {4, 6, 1}, {1, 5, 2}, {6, 5, 1}}
Output: Yes
Explanation: Assign left direction to the first and second segments and right direction to the third and fourth segments.Input: arr[][] = {{1, 2, 3}}
Output: Yes
Approach: The given problem can be solved based on the following observations:
- Case 1: When the speed of two segments are different:
- The idea is to assign the same direction to both the segments.
- Therefore, after a long period of time, the segments will never intersect or overlap. It is possible that between this time, somewhere the segments overlap. Then, eventually one segment will overtake the other.
- Case 2: When the speed of two segments is the same, but they are not intersecting at t = 0:
- The idea is to assign them the same direction of movement to both segments.
- Since their relative position will not change due to same speed and same direction, after infinite time, their relative positions will remain the same and they won’t overlap.
- Case 3: When the speed of two segments is the same, and they overlap / intersect initially.
- The idea is to assign them the opposite direction of movement.
Below examples illustrate all the above cases:
From the above observations, the idea is to create a Graph for all the overlapping segments and check if the created graph is bipartite or not. If the created graph is bipartite, then it is possible to assign directions to all the segments such that they do not intersect after a long period of time. Therefore, print “Yes”. Otherwise, print “No”.
Follow the steps below to solve the problem:
- Generate all possible pairs of distinct elements from the given array arr[][]. If any pair of segments (arr[i], arr[j]) overlap, then add an undirected edge (i, j) between them.
- Check whether the given graph is bipartite or not for all possible nodes over the range [0, N – 1]. If found to be true, then print “Yes”. Otherwise, print “No”.
Below is the implementation of above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Stores the details of the Segment struct Node { int L, R, V; }; // Function to check whether the // graph is bipartite or not bool check(vector< int > Adj[], int Src, int N, bool visited[]) { int color[N] = { 0 }; // Mark source node as visited visited[Src] = true ; queue< int > q; // Push the source vertex in queue q.push(Src); while (!q.empty()) { // Get the front of the queue int u = q.front(); q.pop(); // Assign the color // to the popped node int Col = color[u]; // Traverse the adjacency // list of the node u for ( int x : Adj[u]) { // If any node is visited & // a different colors has been // assigned, then return false if (visited[x] == true && color[x] == Col) { return false ; } else if (visited[x] == false ) { // Set visited[x] visited[x] = true ; // Push the node x // into the queue q.push(x); // Update color of node color[x] = 1 - Col; } } } // If the graph is bipartite return true ; } // Function to add an edge // between the nodes u and v void addEdge(vector< int > Adj[], int u, int v) { Adj[u].push_back(v); Adj[v].push_back(u); } // Function to check if the assignment // of direction can be possible to all // the segments, such that they do not // intersect after a long period of time void isPossible( struct Node Arr[], int N) { // Stores the adjacency list // of the created graph vector< int > Adj[N]; // Generate all possible pairs for ( int i = 0; i < N - 1; i++) { for ( int j = i + 1; j < N; j++) { // If segments do not overlap if (Arr[i].R < Arr[j].L || Arr[i].L > Arr[j].R) { continue ; } // Otherwise, the segments overlap else { if (Arr[i].V == Arr[j].V) { // If both segments have // same speed, then add an edge addEdge(Adj, i, j); } } } } // Keep the track of visited nodes bool visited[N] = { false }; // Iterate for all possible nodes for ( int i = 0; i < N; i++) { if (visited[i] == false && Adj[i].size() > 0) { // Check whether graph is // bipartite or not if (check(Adj, i, N, visited) == false ) { cout << "No" ; return ; } } } // If the graph is bipartite cout << "Yes" ; } // Driver Code int main() { struct Node arr[] = { { 5, 7, 2 }, { 4, 6, 1 }, { 1, 5, 2 }, { 6, 5, 1 } }; int N = sizeof (arr) / sizeof (arr[0]); isPossible(arr, N); return 0; } |
Java
// Java program for the above approach import java.io.*; import java.lang.*; import java.util.*; class GFG{ // Stores the details of the Segment static class Node { int L, R, V; Node( int L, int R, int V) { this .L = L; this .R = R; this .V = V; } } // Function to check whether the // graph is bipartite or not static boolean check(ArrayList<Integer> Adj[], int Src, int N, boolean visited[]) { int color[] = new int [N]; // Mark source node as visited visited[Src] = true ; ArrayDeque<Integer> q = new ArrayDeque<>(); // Push the source vertex in queue q.addLast(Src); while (!q.isEmpty()) { // Get the front of the queue int u = q.removeFirst(); // Assign the color // to the popped node int Col = color[u]; // Traverse the adjacency // list of the node u for ( int x : Adj[u]) { // If any node is visited & // a different colors has been // assigned, then return false if (visited[x] == true && color[x] == Col) { return false ; } else if (visited[x] == false ) { // Set visited[x] visited[x] = true ; // Push the node x // into the queue q.addLast(x); // Update color of node color[x] = 1 - Col; } } } // If the graph is bipartite return true ; } // Function to add an edge // between the nodes u and v static void addEdge(ArrayList<Integer> Adj[], int u, int v) { Adj[u].add(v); Adj[v].add(u); } // Function to check if the assignment // of direction can be possible to all // the segments, such that they do not // intersect after a long period of time static void isPossible(Node Arr[], int N) { // Stores the adjacency list // of the created graph @SuppressWarnings ( "unchecked" ) ArrayList<Integer> [] Adj = (ArrayList<Integer>[]) new ArrayList[N]; // Initialize for ( int i = 0 ; i < N; i++) Adj[i] = new ArrayList<>(); // Generate all possible pairs for ( int i = 0 ; i < N - 1 ; i++) { for ( int j = i + 1 ; j < N; j++) { // If segments do not overlap if (Arr[i].R < Arr[j].L || Arr[i].L > Arr[j].R) { continue ; } // Otherwise, the segments overlap else { if (Arr[i].V == Arr[j].V) { // If both segments have // same speed, then add an edge addEdge(Adj, i, j); } } } } // Keep the track of visited nodes boolean visited[] = new boolean [N]; // Iterate for all possible nodes for ( int i = 0 ; i < N; i++) { if (visited[i] == false && Adj[i].size() > 0 ) { // Check whether graph is // bipartite or not if (check(Adj, i, N, visited) == false ) { System.out.println( "No" ); return ; } } } // If the graph is bipartite System.out.println( "Yes" ); } // Driver Code public static void main(String[] args) { Node arr[] = { new Node( 5 , 7 , 2 ), new Node( 4 , 6 , 1 ), new Node( 1 , 5 , 2 ), new Node( 6 , 5 , 1 ) }; int N = arr.length; isPossible(arr, N); } } // This code is contributed by Kingash |
Python3
# Python3 program for the above approach from collections import deque # Function to check whether the # graph is bipartite or not def check(Adj, Src, N, visited): color = [ 0 ] * N # Mark source node as visited visited = [ True ] * Src q = deque() # Push the source vertex in queue q.append(Src) while ( len (q) > 0 ): # Get the front of the queue u = q.popleft() # q.pop() # Assign the color # to the popped node Col = color[u] # Traverse the adjacency # list of the node u for x in Adj[u]: # If any node is visited & # a different colors has been # assigned, then return false if (visited[x] = = True and color[x] = = Col): return False elif (visited[x] = = False ): # Set visited[x] visited[x] = True # Push the node x # into the queue q.append(x) # Update color of node color[x] = 1 - Col # If the graph is bipartite return True # Function to add an edge # between the nodes u and v def addEdge(Adj, u, v): Adj[u].append(v) Adj[v].append(u) return Adj # Function to check if the assignment # of direction can be possible to all # the segments, such that they do not # intersect after a long period of time def isPossible(Arr, N): # Stores the adjacency list # of the created graph Adj = [[] for i in range (N)] # Generate all possible pairs for i in range (N - 1 ): for j in range (i + 1 , N): # If segments do not overlap if (Arr[i][ 0 ] < Arr[j][ 1 ] or Arr[i][ 1 ] > Arr[j][ 0 ]): continue # Otherwise, the segments overlap else : if (Arr[i][ 2 ] = = Arr[j][ 2 ]): # If both segments have # same speed, then add an edge Adj = addEdge(Adj, i, j) # Keep the track of visited nodes visited = [ False ] * N # Iterate for all possible nodes for i in range (N): if (visited[i] = = False and len (Adj[i]) > 0 ): # Check whether graph is # bipartite or not if (check(Adj, i, N, visited) = = False ): print ( "No" ) return # If the graph is bipartite print ( "Yes" ) # Driver Code if __name__ = = '__main__' : arr = [ [ 5 , 7 , 2 ], [ 4 , 6 , 1 ], [ 1 , 5 , 2 ], [ 6 , 5 , 1 ] ] N = len (arr) isPossible(arr, N) # This code is contributed by mohit kumar 29 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG{ // Stores the details of the Segment class Node { public int L, R, V; }; static Node newNode( int L, int R, int V) { Node temp = new Node(); temp.L = L; temp.R = R; temp.V = V; return temp; } // Function to check whether the // graph is bipartite or not static bool check(List< int > []Adj, int Src, int N, bool []visited) { int []color = new int [N]; // Mark source node as visited visited[Src] = true ; Queue< int > q = new Queue< int >(); // Push the source vertex in queue q.Enqueue(Src); while (q.Count > 0) { // Get the front of the queue int u = q.Peek(); q.Dequeue(); // Assign the color // to the popped node int Col = color[u]; // Traverse the adjacency // list of the node u foreach ( int x in Adj[u]) { // If any node is visited & // a different colors has been // assigned, then return false if (visited[x] == true && color[x] == Col) { return false ; } else if (visited[x] == false ) { // Set visited[x] visited[x] = true ; // Push the node x // into the queue q.Enqueue(x); // Update color of node color[x] = 1 - Col; } } } // If the graph is bipartite return true ; } // Function to add an edge // between the nodes u and v static void addEdge(List< int > []Adj, int u, int v) { Adj[u].Add(v); Adj[v].Add(u); } // Function to check if the assignment // of direction can be possible to all // the segments, such that they do not // intersect after a long period of time static void isPossible(Node []Arr, int N) { // Stores the adjacency list // of the created graph List< int > [] Adj = new List< int >[N]; // Initialize for ( int i = 0; i < N; i++) Adj[i] = new List< int >(); // Generate all possible pairs for ( int i = 0; i < N - 1; i++) { for ( int j = i + 1; j < N; j++) { // If segments do not overlap if (Arr[i].R < Arr[j].L || Arr[i].L > Arr[j].R) { continue ; } // Otherwise, the segments overlap else { if (Arr[i].V == Arr[j].V) { // If both segments have // same speed, then add an edge addEdge(Adj, i, j); } } } } // Keep the track of visited nodes bool []visited = new bool [N]; // Iterate for all possible nodes for ( int i = 0; i < N; i++) { if (visited[i] == false && Adj[i].Count > 0) { // Check whether graph is // bipartite or not if (check(Adj, i, N, visited) == false ) { Console.Write( "No" ); return ; } } } // If the graph is bipartite Console.Write( "Yes" ); } // Driver Code public static void Main() { Node []arr = { newNode(5, 7, 2), newNode(4, 6, 1), newNode(1, 5, 2), newNode(6, 5, 1) }; int N = arr.Length; isPossible(arr, N); } } // This code is contributed by SURENDRA_GANGWAR |
Javascript
<script> // JavaScript program for the above approach // Stores the details of the Segment class Node { constructor(L,R,V) { this .L = L; this .R = R; this .V = V; } } // Function to check whether the // graph is bipartite or not function check(Adj,Src,N,visited) { let color = new Array(N); // Mark source node as visited visited[Src] = true ; let q = []; // Push the source vertex in queue q.push(Src); while (q.length!=0) { // Get the front of the queue let u = q.shift(); // Assign the color // to the popped node let Col = color[u]; // Traverse the adjacency // list of the node u for (let x=0;x< Adj[u].length;x++) { // If any node is visited & // a different colors has been // assigned, then return false if (visited[Adj[u][x]] == true && color[Adj[u][x]] == Col) { return false ; } else if (visited[Adj[u][x]] == false ) { // Set visited[x] visited[Adj[u][x]] = true ; // Push the node x // into the queue q.push(Adj[u][x]); // Update color of node color[Adj[u][x]] = 1 - Col; } } } // If the graph is bipartite return true ; } // Function to add an edge // between the nodes u and v function addEdge(Adj,u,v) { Adj[u].push(v); Adj[v].push(u); } // Function to check if the assignment // of direction can be possible to all // the segments, such that they do not // intersect after a long period of time function isPossible(Arr,N) { // Stores the adjacency list // of the created graph let Adj = new Array(N); // Initialize for (let i = 0; i < N; i++) Adj[i] = []; // Generate all possible pairs for (let i = 0; i < N - 1; i++) { for (let j = i + 1; j < N; j++) { // If segments do not overlap if (Arr[i].R < Arr[j].L || Arr[i].L > Arr[j].R) { continue ; } // Otherwise, the segments overlap else { if (Arr[i].V == Arr[j].V) { // If both segments have // same speed, then add an edge addEdge(Adj, i, j); } } } } // Keep the track of visited nodes let visited = new Array(N); for (let i=0;i<N;i++) visited[i]= false ; // Iterate for all possible nodes for (let i = 0; i < N; i++) { if (visited[i] == false && Adj[i].length > 0) { // Check whether graph is // bipartite or not if (check(Adj, i, N, visited) == false ) { document.write( "No<bR>" ); return ; } } } // If the graph is bipartite document.write( "Yes<br>" ); } // Driver Code let arr=[ new Node(5, 7, 2), new Node(4, 6, 1), new Node(1, 5, 2), new Node(6, 5, 1)]; let N = arr.length; isPossible(arr, N); // This code is contributed by patel2127 </script> |
Yes
Time Complexity: O(N2)
Auxiliary Space: O(N2)