Minimum halls required for class scheduling | Python3 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
MAX = 100001 NEW_LINE def minHalls ( lectures , n ) : NEW_LINE INDENT prefix_sum = [ 0 ] * MAX ; NEW_LINE for i in range ( n ) : NEW_LINE INDENT prefix_sum [ lectures [ i ] [ 0 ] ] += 1 ; NEW_LINE prefix_sum [ lectures [ i ] [ 1 ] + 1 ] -= 1 ; NEW_LINE DEDENT ans = prefix_sum [ 0 ] ; NEW_LINE for i in range ( 1 , MAX ) : NEW_LINE INDENT prefix_sum [ i ] += prefix_sum [ i - 1 ] ; NEW_LINE ans = max ( ans , prefix_sum [ i ] ) ; NEW_LINE DEDENT return ans ; NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT lectures = [ [ 0 , 5 ] , [ 1 , 2 ] , [ 1 , 10 ] ] ; NEW_LINE n = len ( lectures ) ; NEW_LINE print ( minHalls ( lectures , n ) ) ; NEW_LINE DEDENT