Count the number of intervals in which a given value lies | C ++ program to count the number of intervals in which a given value lies ; Function to count the number of intervals in which a given value lies ; Variables to store overall minimum and maximum of the intervals ; Variables to store start and end of an interval ; Frequency array to keep track of how many of the given intervals an element lies in ; Constructing the frequency array ; Driver code ; length of the array
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX_VAL = 200000 ; int countIntervals ( int arr [ ] [ 2 ] , int V , int N ) { int min = INT_MAX ; int max = INT_MIN ; int li , ri ; int freq [ MAX_VAL ] ; for ( int i = 0 ; i < N ; i ++ ) { li = arr [ i ] [ 0 ] ; freq [ li ] = freq [ li ] + 1 ; ri = arr [ i ] [ 1 ] ; freq [ ri + 1 ] = freq [ ri + 1 ] - 1 ; if ( li < min ) min = li ; if ( ri > max ) max = ri ; } for ( int i = min ; i <= max ; i ++ ) freq [ i ] = freq [ i ] + freq [ i - 1 ] ; return freq [ V ] ; } int main ( ) { int arr [ 5 ] [ 2 ] = { { 1 , 10 } , { 5 , 10 } , { 15 , 25 } , { 7 , 12 } , { 20 , 25 } } ; int V = 7 ; int N = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << ( countIntervals ( arr , V , N ) ) ; }