Minimum number of integers required such that each Segment contains at least one of them | Java program for the above approach ; Function to compute minimum number of points which cover all segments ; Sort the list of tuples by their second element . ; To store the solution ; Iterate over all the segments ; Get the start point of next segment ; Loop over all those segments whose start point is less than the end point of current segment ; Print the possibles values of M ; Driver code ; Starting points of segments ; Ending points of segments ; Insert ranges in points [ ] ; Function call
import java . util . * ; class GFG { static void minPoints ( int [ ] [ ] points , int n ) { Arrays . sort ( points , ( a , b ) -> a [ 1 ] - b [ 1 ] ) ; ArrayList < Integer > coordinates = new ArrayList < > ( ) ; int i = 0 ; while ( i < n ) { int seg = points [ i ] [ 1 ] ; coordinates . add ( seg ) ; int p = i + 1 ; if ( p >= n ) break ; int arrived = points [ p ] [ 0 ] ; while ( seg >= arrived ) { p += 1 ; if ( p >= n ) break ; arrived = points [ p ] [ 0 ] ; } i = p ; } for ( Integer point : coordinates ) System . out . print ( point + " ▁ " ) ; } public static void main ( String [ ] args ) { int n = 4 ; int [ ] start = { 4 , 1 , 2 , 5 } ; int [ ] end = { 7 , 3 , 5 , 6 } ; int [ ] [ ] points = new int [ n ] [ 2 ] ; for ( int i = 0 ; i < n ; i ++ ) { points [ i ] [ 0 ] = start [ i ] ; points [ i ] [ 1 ] = end [ i ] ; } minPoints ( points , n ) ; } }