Given a 2D array arr[][], where each row is of the form {start, end} representing the start and endpoints of each line segment on the X-axis. In one step, select a point on the X-axis and delete all the line segments passing through that point. The task is to find the minimum number of such points that need to be selected to delete all the line segments of the array.
Examples:
Input: arr[][]= { {9, 15}, {3, 8}, {1, 6}, {7, 12}, {5,10} }Â
Output : 2Â
Explanation:Â
Select the point arr[2][1](= (6, 0) on the X-axis and delete the second(= arr[1]), third(= arr[2]), and fifth(= arr[4]) line segments.Â
Select the point arr[3][1](= (12, 0)) on the X-axis and delete the first(=arr[0]) and the fourth(=arr[3]) line segments.Â
Therefore, the required count is 2.Input: arr[][]={ {1, 4}, {5, 7}, {9, 13} }Â
Output: 3
Approach: The problem can be solved using the Greedy technique. Follow the steps below to solve the problem:
- Initialize a variable, say cntSteps to count total number of steps required to delete all the line segments.
- Sort the array arr[][] based on the end points of the line segments.
- Initialize a variable, say Points = arr[0][1] to store the points of the X-axis.
- Traverse the array and check if the value of arr[i][0] greater than Points or not. If found to be true then increment the value cntSteps by 1 and update the value of Points = arr[i][1].
- Finally, print the value of cntSteps.
C++
// C++ program to implement// the above approachÂ
Â
#include <bits/stdc++.h>using namespace std;Â
Â
// Comparator functionbool comp(vector<int> &x, vector<int> y){Â Â Â Â return x[1] < y[1];}Â
Â
// Function to count the minimum number of// steps required to delete all the segmentsint cntMinSteps(vector<vector<int> > &arr,                                   int N){     Â
    // Stores count of steps required     // to delete all the line segments    int cntSteps = 1;     Â
    // Sort the array based on end points     // of line segments    sort(arr.begin(), arr.end(), comp);     Â
    // Stores point on X-axis    int Points = arr[0][1];     Â
    // Traverse the array    for(int i = 0; i < N; i++) {         Â
        // If arr[1][0] is         // greater than Points        if(arr[i][0] > Points) {             Â
            // Update cntSteps            cntSteps++;             Â
            // Update Points            Points = arr[i][1];        }    }         return cntSteps;     }Â
Â
// Driver Codeint main() {         vector<vector<int> > arr        = { { 9, 15 }, { 3, 8 },            { 1, 6 }, { 7, 12 },                      { 5, 10 } };                                 int N = arr.size();         cout<< cntMinSteps(arr, N);    return 0;} |
Java
// Java program to implement// the above approachimport java.util.*;Â
class GFG{Â
// Function to sort by column public static void sortbyColumn(int arr[][],                                 int col) {          // Using built-in sort function Arrays.sort     Arrays.sort(arr, new Comparator<int[]>()    {         @Override                 // Compare values according to columns         public int compare(final int[] entry1,                            final int[] entry2)        {                          // To sort in descending order revert             // the '>' Operator             if (entry1[col] > entry2[col])                 return 1;             else                return -1;         }     }); // End of function call sort(). }Â
// Function to count the minimum number of// steps required to delete all the segmentsstatic int cntMinSteps(int[][] arr, int N){         // Stores count of steps required     // to delete all the line segments    int cntSteps = 1;         // Sort the array based on end points     // of line segments    sortbyColumn(arr, 1);         // Stores point on X-axis    int Points = arr[0][1];         // Traverse the array    for(int i = 0; i < N; i++)    {                 // If arr[1][0] is         // greater than Points        if(arr[i][0] > Points)         {                         // Update cntSteps            cntSteps++;                         // Update Points            Points = arr[i][1];        }    }    return cntSteps;}Â
// Driver Codepublic static void main(String[] args){    int[][] arr = { { 9, 15 }, { 3, 8 },                    { 1, 6 }, { 7, 12 },                    { 5, 10 } };                                 int N = arr.length;         System.out.print(cntMinSteps(arr, N));}}Â
// This code is contributed by shikhasingrajput |
C#
// C# program to implement // the above approachclass GFG {    // A C# Function to sort the array by specified column.     static public int[,] Sort_By_Column(int [,] array, int [,] sort_directive)    {        // number of rows inside array        int array_rows = array.GetLength(0);        // number of columns inside array        int array_columns = array.Length/array_rows;        // number of columns to be sorted        int sort_directive_columns = sort_directive.GetLength(0);        //        for(int i=0;i<array_rows-1;i++)        {            for(int j=i+1;j<array_rows;j++)            {                for(int c=0;c<sort_directive_columns;c++)                {                    //                    // sort array values in descending sort order                    //                    if(sort_directive[c,1]==-1 &&                       array[i,sort_directive[c,0]].CompareTo(array[j,sort_directive[c,0]])<0)                    {                        //                        // if values are in ascending sort order                        // swap values                        //                        for(int d=0;d<array_columns;d++)                        {                            int h = array[j,d];                            array[j,d]=array[i,d];                            array[i,d]=h;                        }Â
                        break;                    }                    //                    // if values are in correct sort order break                    //                    else if(sort_directive[c,1]==-1 &&                            array[i,sort_directive[c,0]].CompareTo(array[j,sort_directive[c,0]])>0)                        break;                    //                    // sort array values in ascending sort order                    //                    else if(sort_directive[c,1]==1 &&                            array[i,sort_directive[c,0]].CompareTo(array[j,sort_directive[c,0]])>0)                    {                        //                        // if values are in descending sort order                        // swap values                        //                        for(int d=0;d<array_columns;d++)                        {                            int h = array[j,d];                            array[j,d]=array[i,d];                            array[i,d]=h;                        }Â
                        break;                    }                    //                    // if values are in correct sort order break                    //                    else if(sort_directive[c,1]==1 &&                            array[i,sort_directive[c,0]].CompareTo(array[j,sort_directive[c,0]])<0)                        break;                    //                    // if values are equal                    // select next sort directive                    //                }            }        }Â
        return array;    }              // Function to count the minimum number of    // steps required to delete all the segments    static public int cntMinSteps(int [,]arr, int N)    {Â
        // Stores count of steps required        // to delete all the line segments        int cntSteps = 1;Â
        // Sort the array based on end points        // of line segments        int [,] SORT_DIRECTIVE=new int[1,2]{            {1, 1}        };        Sort_By_Column(arr, SORT_DIRECTIVE);                 // Stores point on X-axis        int Points = arr[0,1];Â
        // Traverse the array        for (int i = 0; i < N; i++) {Â
            // If arr[1][0] is            // greater than Points            if (arr[i,0] > Points) {Â
                // Update cntSteps                cntSteps = cntSteps + 1;Â
                // Update Points                Points = arr[i,1];            }        }Â
        return cntSteps;    }Â
    // Driver code    static void Main()    {        int[,] arr = new int[,]{ { 9, 15 },                                 { 3, 8 },                                 { 1, 6 },                                 { 7, 12 },                                 { 5, 10 } };        int N = arr.GetLength(0);        System.Console.WriteLine(cntMinSteps(arr, N));    }}Â
// The code is contributed by Gautam goel (gautamgoel962) |
Python3
# Python3 program to implement# the above approachÂ
# Comparator functiondef comp(x, y):    return x[1] < y[1]   # Function to count the # minimum number of steps # required to delete all # the segmentsdef cntMinSteps(arr, N):       # Stores count of steps     # required to delete all     # the line segments    cntSteps = 1Â
    # Sort the array based     # on end points of line     # segments    arr.sort(reverse = False)   Â
    # Stores point on X-axis    Points = arr[0][1]   Â
    # Traverse the array    for i in range(N):               # If arr[1][0] is         # greater than Points        if(arr[i][0] > Points):                       # Update cntSteps            cntSteps += 1                         # Update Points            Points = arr[i][1]         return cntStepsÂ
# Driver Codeif __name__ == '__main__':Â Â Â Â Â Â Â arr = [[9, 15], [3, 8], Â Â Â Â Â Â Â Â Â Â Â [1, 6], [7, 12], Â Â Â Â Â Â Â Â Â Â Â [5, 10]]Â Â Â Â Â Â Â Â Â Â Â Â Â Â Â N = len(arr)Â Â Â Â print(cntMinSteps(arr, N))Â
# This code is contributed by bgangwar59 |
Javascript
<script>Â
// JavaScript program to implement// the above approachÂ
// Comparator functionfunction comp(x, y){Â Â Â Â return x[1] - y[1]}Â
// Function to count the// minimum number of steps// required to delete all// the segmentsfunction cntMinSteps(arr, N){Â
    // Stores count of steps    // required to delete all    // the line segments    let cntSteps = 1Â
    // Sort the array based    // on end points of line    // segments    arr.sort(comp)Â
    // Stores point on X-axis    let Points = arr[0][1]Â
    // Traverse the array    for(let i=0;i<N;i++){             // If arr[1][0] is        // greater than Points        if(arr[i][0] > Points){                     // Update cntSteps            cntSteps += 1                         // Update Points            Points = arr[i][1]        }    }         return cntSteps}Â
// Driver CodeÂ
let   arr = [[9, 15], [3, 8],        [1, 6], [7, 12],        [5, 10]]       let   N = arr.lengthdocument.write(cntMinSteps(arr, N))Â
// This code is contributed by shinjanpatraÂ
</script> |
Output:Â
2
Â
Time Complexity: O(N * log(N)), for using inbuilt sort() function.
Auxiliary Space: O(1), constant extra space is required.
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!
