- Geometric, Geometric-Lines, Greedy, Mathematical, Sorting

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: NOExplanation: 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 : YESApproach : 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#include using namespace std;  void findIfPossible(int n, int k,                    vector position){      sort(position.begin(), position.end());      int ans = 1;              int r = position[0][1];          for (int i = 1; i < n; i++) {          if (position[i][0] = ans)        cout