Count of available non | C ++ implementation of the above approach ; Function to find the pivot index ; Function to implement Quick Sort ; Pivot is pointing to pivot index before which every element is smaller and after pivot , every element is greater ; Sort the array before pivot element ; Sort the array after pivot element ; Function to count the available intervals from the given range of numbers ; If range starts after 0 then an interval is available from 0 to start [ 0 ] ; When a new interval starts ; Since index variable i is being incremented , the current active interval will also get incremented ; When the current interval ends ; Since index variable j is being decremented , the currect active interval will also get decremented ; When start and end both are same there is no change in currActive ; If the end of interval is before the range so interval is available at the end ; Driver code ; Sort the start array ; Sort the end array ; Calling the function
#include <iostream> NEW_LINE using namespace std ; int partition ( int arr [ ] , int l , int h ) { int pivot = arr [ l ] ; int i = l + 1 ; int j = h ; while ( i <= j ) { while ( i <= h && arr [ i ] < pivot ) { i ++ ; } while ( j > l && arr [ j ] > pivot ) { j -- ; } if ( i < j ) { int temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; i ++ ; j -- ; } else i ++ ; } arr [ l ] = arr [ j ] ; arr [ j ] = pivot ; return j ; } void sortArray ( int arr [ ] , int l , int h ) { if ( l >= h ) return ; int pivot = partition ( arr , l , h ) ; sortArray ( arr , l , pivot - 1 ) ; sortArray ( arr , pivot + 1 , h ) ; } int findMaxIntervals ( int start [ ] , int end [ ] , int n , int R ) { int ans = 0 ; int prev = 0 ; int currActive = 0 ; int i = 0 ; int j = 0 ; if ( start [ 0 ] > 0 ) ans ++ ; while ( i < n && j < n ) { if ( start [ i ] < end [ j ] ) { i ++ ; currActive ++ ; } else if ( start [ i ] > end [ j ] ) { j ++ ; currActive -- ; } else { i ++ ; j ++ ; } if ( currActive == 0 ) { ans ++ ; } } if ( end [ n - 1 ] < R ) ans ++ ; return ans ; } int main ( ) { int R , N ; R = 10 ; N = 3 ; int start [ N ] = { 2 , 5 , 8 } ; int end [ N ] = { 3 , 9 , 10 } ; sortArray ( start , 0 , N - 1 ) ; sortArray ( end , 0 , N - 1 ) ; cout << findMaxIntervals ( start , end , N , R ) ; }