You are given a list of boxes with 2 dimensions, width and height. Return the maximum number of boxes you can stack on each other. You can rotate the box so basically if you have a box with dimensions [3,2] you can turn it into [2,3]. You can only put the box on the top of the pile if the width is less than the width of the current box on the pile.

Ex:
input is [width,height]
[2,2],[3,2],[3,4],[4,3]: result=3, start with either of the boxes that have a 4, then take the [3,2] width 3, then take the [2,2] on top. Cannot use both the [3,4] and [4,3] regardless of rotation.

Don't think I did that well on this one. Initially I thought I should do a greedy type solution where you sort by both dimensions to create 2 sorted lists, then try to always put the biggest box you find. Solution I eventually came up with is based on the intuition that you just need to create a set to record the widths that have been used. Do not need to start from bottom up because for the purposes of this problem, you can just insert into the stack as if you laid it perfectly. So in above example, say I start with [2,2], record width 2 into seen stack, proceed to [3,2]. Witdh 3 has not been used, record seen 3. Proceed to [3,4], width 3 has been used. But I can rotate, and width 4 has not been used.

Something like this

seen=set()
res=0
for i in range(len(stack)):
	width,height=stack[i]
	if width in seen and height in seen: continue
	if width in seen:
		seen.add(height)
	else:
		seen.add(width)
		
	res+=1
return res

Only thing that tripped me up and made me doubt was the interviewer asked in the above scenario if width and height are both not yet seen, which do you add? Which is more optimal? I said it doesnt matter which you add but am not sure. It was hard for me to come up with a test example where it mattered which dimension to use if you didn't use either yet. I thought maybe the biggest dimension is more optimal to use first so that in the future you maximize chances of stacking, but am still doubting. Is there a better way?

Might have screwed up an easy question