This is the "best-worst conjoint" as invented by Jordan Louviere. We sometimes refer to this as MaxDiff with "conjoint-style" prohibitions. It's a particular way to do something that is in-between conjoint analysis and MaxDiff. (By the way, best-worst conjoint has generally not tested as well as bonafide conjoint analysis.)
Interestingly enough, Jordan originally envisioned MaxDiff to be done within a conjoint context with multiple attributes and multiple levels as you've described. But, the method didn't perform better than standard conjoint, as tested by others. BUT, the MaxDiff idea was a nice one, and it took off with respect to scaling an array of items.
Now, regarding your sample size question: I'm sorry, but there isn't a good answer. Sample size requirements depend on so many factors, including your budget, how expensive each interview is to collect, how large the universe is that your projecting to, and your tolerance for sampling error.
Some exploratory research uses sample sizes as low as n=20 or 30. Larger consumer research that requires a low tolerance for sampling error will have n=1000 or more.