Minimum distance to travel to cover all intervals | C ++ program to find minimum distance to travel to cover all intervals ; structure to store an interval ; Method returns minimum distance to travel to cover all intervals ; looping over all intervals to get right most start and left most end ; if rightmost start > leftmost end then all intervals are not aligned and it is not possible to cover all of them ; if x is in between rightmoststart and leftmostend then no need to travel any distance ; choose minimum according to current position x ; Driver code to test above methods
#include <bits/stdc++.h> NEW_LINE using namespace std ; struct Interval { int start , end ; Interval ( int start , int end ) : start ( start ) , end ( end ) { } } ; int minDistanceToCoverIntervals ( Interval intervals [ ] , int N , int x ) { int rightMostStart = INT_MIN ; int leftMostEnd = INT_MAX ; for ( int i = 0 ; i < N ; i ++ ) { if ( rightMostStart < intervals [ i ] . start ) rightMostStart = intervals [ i ] . start ; if ( leftMostEnd > intervals [ i ] . end ) leftMostEnd = intervals [ i ] . end ; } int res ; if ( rightMostStart > leftMostEnd ) res = -1 ; else if ( rightMostStart <= x && x <= leftMostEnd ) res = 0 ; else res = ( x < rightMostStart ) ? ( rightMostStart - x ) : ( x - leftMostEnd ) ; return res ; } int main ( ) { int x = 3 ; Interval intervals [ ] = { { 0 , 7 } , { 2 , 14 } , { 4 , 6 } } ; int N = sizeof ( intervals ) / sizeof ( intervals [ 0 ] ) ; int res = minDistanceToCoverIntervals ( intervals , N , x ) ; if ( res == -1 ) cout << " Not ▁ Possible ▁ to ▁ cover ▁ all ▁ intervals STRNEWLINE " ; else cout << res << endl ; }