This is the "Queue Reconstruction by Height" problem from leetcode.com:

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

 

Note: The number of people is less than 1100.

Suppose I take only the tallest persons, all having the same maximum height. Their second values must be 0, 1, 2, 3... with no gaps at all, because they only count each other. Therefore, if there were no other persons at all, their second value must be their final index. What about the persons with second maximum height then? Suppose there are only tallest persons and just one more person who has slightly smaller height. What would be his position? Well, since he obviously only count tallest persons, his position would still be his second value. The next person of the same height counts only the previous person and all the tallest ones, but since they are all already in the queue, his second value would also be his index.

import collections

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        d = collections.defaultdict(list)
        for height, count in people:
            d[height] += [count]
        
        recon_q = []
        for height, counts in sorted(d.items(), key = lambda x:x[0], reverse=True):
            for count in sorted(counts):
                recon_q.insert(count, [height, count])
        return recon_q

Is there any better data structure that can be used? I feel there must be a better way to do sorting here.

Note that the Solution class is required by LeetCode, even though it has no other function.

This is the "Queue Reconstruction by Height" problem from leetcode.com:

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1100.

Suppose I take only the tallest persons, all having the same maximum height. Their second values must be 0, 1, 2, 3... with no gaps at all, because they only count each other. Therefore, if there were no other persons at all, their second value must be their final index. What about the persons with second maximum height then? Suppose there are only tallest persons and just one more person who has slightly smaller height. What would be his position? Well, since he obviously only count tallest persons, his position would still be his second value. The next person of the same height counts only the previous person and all the tallest ones, but since they are all already in the queue, his second value would also be his index.

import collections

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        d = collections.defaultdict(list)
        for height, count in people:
            d[height] += [count]
        
        recon_q = []
        for height, counts in sorted(d.items(), key = lambda x:x[0], reverse=True):
            for count in sorted(counts):
                recon_q.insert(count, [height, count])
        return recon_q

Is there any better data structure that can be used? I feel there must be a better way to do sorting here.

Note that the Solution class is required by LeetCode, even though it has no other function.

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

Note: The number of people is less than 1100.

problem: Solution:

Suppose I take only the tallest persons, all having the same maximum height. Their second values must be 0, 1, 2, 3... with no gaps at all, because they only count each other. Therefore, if there were no other persons at all, their second value must be their final index. What about the persons with second maximum height then? Suppose there are only tallest persons and just one more person who has slightly smaller height. What would be his position? Well, since he obviously only count tallest persons, his position would still be his second value. The next person of the same height counts only the previous person and all the tallest ones, but since they are all already in the queue, his second value would also be his index.

import collections

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        d = collections.defaultdict(list)
        for height, count in people:
            d[height] += [count]
        
        recon_q = []
        for height, counts in sorted(d.items(), key = lambda x:x[0], reverse=True):
            for count in sorted(counts):
                recon_q.insert(count, [height, count])
        return recon_q

Is there any better data structure that can be used? I feel there must be a better way to do sorting here.

Class is used as it is standard in leetcode problems. So please avoid it.

This is the "Queue Reconstruction by Height" problem from leetcode.com:

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.

 

Note: The number of people is less than 1100.

Suppose I take only the tallest persons, all having the same maximum height. Their second values must be 0, 1, 2, 3... with no gaps at all, because they only count each other. Therefore, if there were no other persons at all, their second value must be their final index. What about the persons with second maximum height then? Suppose there are only tallest persons and just one more person who has slightly smaller height. What would be his position? Well, since he obviously only count tallest persons, his position would still be his second value. The next person of the same height counts only the previous person and all the tallest ones, but since they are all already in the queue, his second value would also be his index.

import collections

class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        d = collections.defaultdict(list)
        for height, count in people:
            d[height] += [count]
        
        recon_q = []
        for height, counts in sorted(d.items(), key = lambda x:x[0], reverse=True):
            for count in sorted(counts):
                recon_q.insert(count, [height, count])
        return recon_q

Is there any better data structure that can be used? I feel there must be a better way to do sorting here.

Note that the Solution class is required by LeetCode, even though it has no other function.