Minimum halls required for class scheduling | C ++ implementation of the approach ; Function to return the minimum number of halls required ; Array to store the number of lectures ongoing at time t ; For every lecture increment start point s decrement ( end point + 1 ) ; Perform prefix sum and update the ans to maximum ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MAX  100001 NEW_LINE int minHalls ( int lectures [ ] [ 2 ] , int n ) { int prefix_sum [ MAX ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { prefix_sum [ lectures [ i ] [ 0 ] ] ++ ; prefix_sum [ lectures [ i ] [ 1 ] + 1 ] -- ; } int ans = prefix_sum [ 0 ] ; for ( int i = 1 ; i < MAX ; i ++ ) { prefix_sum [ i ] += prefix_sum [ i - 1 ] ; ans = max ( ans , prefix_sum [ i ] ) ; } return ans ; } int main ( ) { int lectures [ ] [ 2 ] = { { 0 , 5 } , { 1 , 2 } , { 1 , 10 } } ; int n = sizeof ( lectures ) / sizeof ( lectures [ 0 ] ) ; cout << minHalls ( lectures , n ) ; return 0 ; }