Given a sequence of jobs executed by a machine. What is the maximum number of parallel jobs executed at any point of time.
One more variation of this problem can be
Given a maximum capacity of a computer center, and a sequence of people arrived, how many people have to wait for their turn.
Check this question for details.
- Take two variables depth and max_depth initialize them to zero.
- Increment depth if we see an open bracket and update the max_depth
- Decrement depth if we see a closed bracket and check if it is going negative.If it goes negative, the expression is unbalanced.
- Check if depth is zero. If it is not zero, then it is not a balanced expression.
- Return max_depth
Here is the Python implementation.The time complexity for this O(n) and space complexity is O(1).