Minimum number of integers required such that each Segment contains at least one of them | C ++ program for the above approach ; function to sort the 2D vector on basis of second element . ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; bool sortcol ( const pair < int , int > p1 , const pair < int , int > p2 ) { return p1 . second < p2 . second ; } void minPoints ( pair < int , int > points [ ] , int n ) { sort ( points , points + n , sortcol ) ; vector < int > coordinates ; int i = 0 ; while ( i < n ) { int seg = points [ i ] . second ; coordinates . push_back ( seg ) ; int p = i + 1 ; if ( p >= n ) break ; int arrived = points [ p ] . first ; while ( seg >= arrived ) { p += 1 ; if ( p >= n ) break ; arrived = points [ p ] . first ; } i = p ; } for ( auto point : coordinates ) cout << point << " ▁ " ; } int main ( ) { int n = 4 ; int start [ ] = { 4 , 1 , 2 , 5 } ; int end [ ] = { 7 , 3 , 5 , 6 } ; pair < int , int > points [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { points [ i ] = { start [ i ] , end [ i ] } ; } minPoints ( points , n ) ; return 0 ; }