Minimum number of intervals to cover the target interval | C ++ program for the above approach ; Function to find the minimum number of intervals in the array A [ ] to cover the entire target interval ; Sort the array A [ ] in increasing order of starting point ; Insert a pair of INT_MAX to prevent going out of bounds ; Stores start of current interval ; Stores end of current interval ; Stores the count of intervals ; Iterate over all the intervals ; If starting point of current index <= start ; Update the value of start ; Increment the value of count ; If the target interval is already covered or it is not possible to move then break the loop ; If the entire target interval is not covered ; Return Answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int minimizeSegment ( vector < pair < int , int > > A , pair < int , int > X ) { sort ( A . begin ( ) , A . end ( ) ) ; A . push_back ( { INT_MAX , INT_MAX } ) ; int start = X . first ; int end = X . first - 1 ; int cnt = 0 ; for ( int i = 0 ; i < A . size ( ) ; ) { if ( A [ i ] . first <= start ) { end = max ( A [ i ++ ] . second , end ) ; } else { start = end ; ++ cnt ; if ( A [ i ] . first > end end >= X . second ) { break ; } } } if ( end < X . second ) { return -1 ; } return cnt ; } int main ( ) { vector < pair < int , int > > A = { { 1 , 3 } , { 2 , 4 } , { 2 , 10 } , { 2 , 3 } , { 1 , 1 } } ; pair < int , int > X = { 1 , 10 } ; cout << minimizeSegment ( A , X ) ; return 0 ; }