Check if N given lines can be intersected by K vertical lines
Given N horizontal lines represented by an array position[][] of size N, where position[i] represents the ith horizontal line which has x-coordinates from position[i][0] to position[i][1] and an integer K, which represents the maximum number of vertical lines that can be drawn, the task is to check if N given lines can be intersected by at most K vertical lines.
Examples:
Input: N = 4, K = 2, position[][] = [[1, 4], [6, 8], [7, 9], [10, 15]]
Output: NO
Explanation: In the given example, draw lines at [1, 7, 10]. The line drawn at 1 will intersect the first line, the line at position 7 will intersect both the second and third lines, and the line drawn at 10 will intersect the fourth line. Hence, a minimum of 3 rods is required. Hence, it is not possibleInput: N = 5, K = 3, position[][] = [[1, 6], [3, 5], [2, 4], [8, 12], [10, 24]]
Output : YES
Approach : The idea is to use greedy approach to solve this problem by sorting the positions[][] array and, with 1 line, intersect as many lines as possible and so on. Follow the steps below to solve the problem:
- Sort the array position[][] in ascending order.
- Initialize the variables ans as 1 to store the answer and r as position[0][1] to store the end point till a particular point other horizontal lines can be for intersection with the given considered vertical line.
- Iterate over the range [1, N] using the variable, say I, and perform the following steps:
- If position[i][0] is less than r, then set the value of r to the minimum of r or position[i][1].
- Otherwise, add the value of ans by 1 and set the value of r as position[i][1].
- If k is greater than equal to ans, then print “YES” and print “NO” otherwise.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if it is possible // to intersect n lines using k vertical lines void findIfPossible( int n, int k, vector<vector< int > > position) { sort(position.begin(), position.end()); int ans = 1; // Track the point till a particular // vertical line can intersect int r = position[0][1]; // Iterate over the range for ( int i = 1; i < n; i++) { if (position[i][0] <= r) { r = min(r, position[i][1]); } else { ans++; r = position[i][1]; } } if (k >= ans) cout << "YES" << endl; else cout << "NO" << endl; } // Driver Code int main() { int n = 5; int k = 2; vector<vector< int > > position = { { 2, 5 }, { 4, 6 }, { 7, 16 }, { 9, 10 }, { 10, 17 } }; findIfPossible(n, k, position); return 0; } |
Java
// Java program for the above approach import java.util.*; class GFG { // Function to check if it is possible // to intersect n lines using k vertical lines static void findIfPossible( int n, int k, int [][] position) { Arrays.sort(position, Comparator.comparingDouble(o -> o[ 0 ])); int ans = 1 ; // Track the point till a particular // vertical line can intersect int r = position[ 0 ][ 1 ]; // Iterate over the range for ( int i = 1 ; i < n; i++) { if (position[i][ 0 ] <= r) { r = Math.min(r, position[i][ 1 ]); } else { ans++; r = position[i][ 1 ]; } } if (k >= ans) System.out.println( "YES" ); else System.out.println( "NO" ); } // Driver Code public static void main(String[] args) { int n = 5 ; int k = 2 ; int [][] position = { { 2 , 5 }, { 4 , 6 }, { 7 , 16 }, { 9 , 10 }, { 10 , 17 } }; findIfPossible(n, k, position); } } // This code is contributed by sanjoy_62. |
Python3
# python program for the above approach # Function to check if it is possible # to intersect n lines using k vertical lines def findIfPossible(n, k, position): position.sort() ans = 1 # Track the point till a particular # vertical line can intersect r = position[ 0 ][ 1 ] # Iterate over the range for i in range ( 1 , n): if (position[i][ 0 ] < = r): r = min (r, position[i][ 1 ]) else : ans + = 1 r = position[i][ 1 ] if (k > = ans): print ( "YES" ) else : print ( "NO" ) # Driver Code n = 5 k = 2 position = [[ 2 , 5 ], [ 4 , 6 ], [ 7 , 16 ], [ 9 , 10 ], [ 10 , 17 ]] findIfPossible(n, k, position) # This code is contributed by amreshkumar3 |
C#
// C# program for the above approach using System; class GFG{ static void Sort( int [,] arr) { for ( int i = 0; i < arr.GetLength(0); i++) { for ( int j = arr.GetLength(1) - 1; j > 0; j--) { for ( int k = 0; k < j; k++) { if (arr[i, k] > arr[i, k + 1]) { int myTemp = arr[i, k]; arr[i, k] = arr[i, k + 1]; arr[i, k + 1] = myTemp; } } } } } // Function to check if it is possible // to intersect n lines using k vertical lines static void findIfPossible( int n, int k, int [,] position) { Sort(position); int ans = 1; // Track the point till a particular // vertical line can intersect int r = position[0, 1]; // Iterate over the range for ( int i = 1; i < n; i++) { if (position[i, 0] <= r) { r = Math.Min(r, position[i, 1]); } else { ans++; r = position[i, 1]; } } if (k >= ans) Console.Write( "YES" ); else Console.Write( "NO" ); } // Driver Code public static void Main( string [] args) { int n = 5; int k = 2; int [,] position = { { 2, 5 }, { 4, 6 }, { 7, 16 }, { 9, 10 }, { 10, 17 } }; findIfPossible(n, k, position); } } // This code is contributed by code_hunt |
Javascript
<script> // javascript program for the above approach // Function to check if it is possible // to intersect n lines using k vertical lines function findIfPossible(n, k, position) { position = position.sort( function (a, b) { return a[0]-b[0] }); var i; var ans = 1; // Track the point till a particular // vertical line can intersect var r = position[0][1]; // Iterate over the range for (i = 1; i < n; i++) { if (position[i][0] <= r) { r = Math.min(r, position[i][1]); } else { ans++; r = position[i][1]; } } if (k >= ans) document.write( "YES" ); else document.write( "NO" ); } // Driver Code var n = 5; var k = 2; var position = [[2, 5],[4, 6], [7, 16],[9, 10],[10, 17]]; findIfPossible(n, k, position); // This code is contributed by SURENDRA_GANGWAR. </script> |
YES
Time Complexity: O(NlogN)
Auxiliary Space: O(1)