LeetCode: Queue Reconstruction by Height C#
API

I assume it's part of the platform requirements, but int[] is a terrible data-structure for storing the (k, h) pair, because it could have any length and implies an ordering that doesn't really exist. This should be a small class or immutable struct. (Not a Tuple, because Tuples are structural, and therefore only solve part of the problem).

Even if this was imposed upon me, I would want to map it to something sensible before doing anything else. This mapping would act as a (necessary) validation layer, to check I'm not being given nonsense.

ReconstructQueueList

This should document what it does.

I don't see the point in initialising every element of res, when you could just assign them a copy of the existing person array when you set them. This makes the code much tidier. I would move the declaration of res toward where it is actually used.

list is a completely meaningless variable name. These are the positions in the queue that you have yet to be assigned, so I will call it positions; however, I'm sure you can think of something much better. I would create positions with Enumerable.Range(0, people.Length), which is more compact and has less scope for errors. I doubt the added overhead will be significant, but feel free to measure it.

PairComparer

PairComparer is not a fantastic name for something that sorts people.

It's good that you've given some description of what the custom comparer does. However, I don't understand the description you provide.

I'd prefer to see x[0].CompareTo(y[0]) instead of x[0] = y[0]: it's much clearer what is going on, and it doesn't risk overflowing for numbers with large magnitude.

Performance

This section is pretty underwhelming

If we ignore the problem size limit of 1100 (where did they find that number?), the main performance concern is the List.Remove(int) calls, which means this algorithm is quadratic in the worst case (though linear in the best case). You can address this by using a data-structure which allows log(n) removal by index. I threw together a simple OrderedShrinkList, where removing every has a cost of n log(n) and n is the number of elements with which it begins, and ran some benchmarks.

Swapping this appears to give a significant performance boost for large problems: it is 10 times faster on a particular random instance of size 200000 gist of code and results (it seems to be slower for smaller ones).

Running small problems (e.g. size 1100 and smaller), the potential inefficiency of List based method is not immediately revealed, and the overhead of my shoddy OrderedShrinkList seems to make it significantly slower. I've run out of energy to keep trying things, but a linked list might actually improve things, because it replacing a linear 'move' with a linear scan, and you can choose at which end to start.

Note: I did run benchmark for some different seeds, and the general trend was similar, but this isn't the most rigorous test ever.