Queue reconstruction by height
There are two difficulties here:


The input needs to be sorted in decreasing order by height, but increasing order by count. The code in the post handles this by collating the input by height and then sorting twice: first in reverse order by height, and then for a given height in normal order by count.

This could be simplified by passing a key function to sorted so that it sorts in the required order. In particular, if take the key to be (-height, count) then the list will sort into the required order without any need for collation.

def _queue_key(person):
    height, count = person
    return -height, count

def reconstruct_queue_2(people):
    result = []
    for person in sorted(people, key=_queue_key):
        _, count = person
        result.insert(count, person)
    return result

Inserting an item into the middle a list takes time proportional to the length of the list (see the TimeComplexity page in the Python wiki). This means that the reconstruction algorithm takes time that's quadratic in the length of the queue. It would nice to do better than this.

The data structure that's needed here is some kind of balanced tree. Python doesn't have anything suitable in the standard library, but the sortedcontainers package from the Python Package Index has a SortedListWithKey class that can do what we need.

from sortedcontainers import SortedListWithKey

def reconstruct_queue_3(people):
    result = SortedListWithKey(key=lambda _:0)
    for person in sorted(people, key=_queue_key):
        _, count = person
        result.insert(count, person)
    return result


This is slightly tricksy code because we're not making use of the "sorted" property of the SortedListWithKey class — we use the key= argument to make all the items identical as far as sort order is concerned. We're using the class only to get efficient insertion at an arbitrary index in a list.