We look at each string separately, since they are mutually independent. For each string, we will simulate the events on that string.

We will store the sequence of currently pressed frets, in ascending order. When a new fret is to be pressed, we must remove all the fingers from higher frets that are already pressed. We do this by removing the elements one by one from the back of the sequence until we have reached the lower fret, or the sequence becomes empty. Then we can safely append the new fret to the sequence.

Since each pressing is present exactly once in the sequence, this algorithm has linear complexity.

This kind of sequence, where elements are only added to and removed from the end, is called a stack.