Space saving dish washing

Question

There are some stacks of dishes on the left side of the sink. There aren't any on the right side. A larger dish can never go on top of a smaller dish (this is valid for all stacks on both left and right sides of the sink).

The only thing you may do is take a dish from the top of one stack on the left side, wash it, and place it anywhere on the right side of the sink (given that it doesn't violate the rule above).

What strategy should you use such that once all the dishes are washed, the right side has the least amount of stacks possible?

Specifics: To simplify the problem, all dishes have distinct sizes.

Example:

You start with two stacks: 4,1 and 3,2

A possible minimum solution is washing dishes in this order: 2,1,4,3

You end up with two stacks: 2,1 and 4,3

Answer 1

The minimum number of stacks on the right is

the same as the height of the tallest stack on the left.

Proof and strategy:

First of all, the minimum number of stacks on the right is at least that large, because there is no way to get two dishes from a single LH stack into the same RH stack. (Because when you wash any of them, no larger dish from that stack is yet on the right.)

And

the minimum number of stacks on the right is at most that large, and here's an easy strategy: Take the top dish from each LH stack, largest first, and form them into a single RH stack. Repeat until you've washed all the dishes.